Make Triangle （卡特兰数）

Time limit 10000 msMemory limit 165888 kB

数论

Description

给出一个凸n边形，求用n-3条不相交的对角线将该n边形划分为三角形的方案数

Input

First line of the input will be an integer t (1<=t<=100000) which is the no of test cases. Each test case contains a single integer n (3<=n<=1000) which is the size of the polygon.

Output

For each test case output the no of ways %100007.

Example

Input:

2
3
5

Output:

1
5

题意：

题意是明了的......

解题思路：

卡特兰数，，具体的我并不知道；其实我只想记个代码//
卡特兰数：
1、通项公式：h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!)
2、递推公式:h(n)=((4*n-2)/(n+1))*h(n-1);  
h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0).
3、前几项为：h(0)=1,h(1)=1,h(2)=2,h(3)=5,h(4)=14,h(5)=42,......

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
ll h[1010];
int main()
{
    h[0]=1;h[1]=1;
    for(int i=2;i<1005;i++)
        for(int j=0;j<i;j++)
        {
            h[i]+=h[j]*h[i-j-1];
            h[i]=h[i]%100007;
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n;
            scanf("%d",&n);
            printf("%lld\n",h[n-2]);
        }
    return 0;
}