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.