CGY杯

火车出站（卡特兰数）

Problem Description
CGY管理着一个火车站的调度问题，这个车站有个中转站，可以停靠任意多节的火车，但末端封顶，驶入中转站的火车必须按照相反的顺序驶出。现在有N节火车，编号为1~N，这些火车按照1,2,3…N的顺序进站。CGY每天看着这些火车真的很无聊，他现在在想这些火车会有多少种出站顺序。
Input
输入的第一行是一个整数T,表示有T(1≤T≤100)组数据
接下来包含T行，每行一个整数N(1≤N≤35)，表示火车的节数。
Output
输出T行，每行一个整数，表示可能的出站顺序

Sample Input
3
1
2
3

Sample Output
1
2
5

解释

卡特兰数的一般公式
卡特兰数满足以下性质：
令h(0)=1,h(1)=1，catalan数满足递推式。h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)h(0) (n>=2)。也就是说，如果能把公式化成上面这种形式的数，就是卡特兰数。
当然，上面这样的递推公式太繁琐了，于是数学家们又求出了可以快速计算的通项公式。h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)。这个公式还可以更简单得化为h(n)=C(2n,n)/(n+1)。后一个公式都可以通过前一个公式经过几步简单的演算得来，大家可以拿起笔试试，一两分钟就可以搞定。

模板

f[0]=f[1]=1;
for(int i=2;i<=n;i++)
    for(int j=0;j<i;j++)
        f[i]+=f[j]*f[i-j-1];

注意

卡特兰数第35项刚好比long long小一点，但用不同的递推式中途数据long long可能会爆掉.

代码

#include <bits/stdc++.h>
using namespace std;
long long int d[36];

void checked(){
 d[0]=d[1]=1;
    for(int i=2;i<=35;i++)
        for(int j=0;j<i;j++){
            d[i]+=d[j]*d[i-j-1];
        }
}

int main(){
    int T,n;
    checked();
    cin>>T;
    while(T--){
        scanf("%d",&n);
        printf("%lld\n",d[n]);
    }
    return 0;
}