2017.1.16【初中部 】普及组模拟赛C组 cirs 题解

原题：

http://172.16.0.132/junior/#contest/show/1366/2

题目描述：

Czyzoiers都想知道小x为什么对鸡蛋饼情有独钟。经过一番逼问，小x道出了实情：因为他喜欢圆。最近小x又发现了一个关于圆的有趣的问题：在圆上有2N个不同的点，小x想用N条线段把这些点连接起来（每个点只能连一条线段），使所有的线段都不想交，他想知道这样的连接方案有多少种？

输入：

有且仅有一个正整数N。

输出：

要求的方案数（结果mod 100000007）。

样例输入：

样例输入1：

2

样例输入2：

3

样例输入3：

24

样例输出：

样例输出1：

2

样例输出2：

5

样例输出3：

4057031

数据范围限制：

对于30%的数据：N<=5。

对于60%的数据：N<=10。

对于100%的数据：N<=3000。

提示&样例2解释：

分析：

这道题我们可以用dp，f[i]表示当圆有2*i个点时，有f[i]种连接方案；

则：

f[0]=1;f[1]=1;f[2]=2;

f[i]=(f[i]+f[i-j]*f[j-1])%100000007;

实现：

var
        i,j,n:longint;
        f:array[..]of int64;
begin
        assign(input,'cirs.in');reset(input);
        assign(output,'cirs.out');rewrite(output);
        readln(n);
        f[0]:=;
        f[1]:=;
        f[2]:=;
        for i:= to n do
                for j:= to i do
                        f[i]:=(f[i]+f[i-j]*f[j-])mod ;
        writeln(f[n] mod );
        close(input);close(output);
end.