csu 10月 月赛 B 题 Scoop water

一个卡特兰数的应用；

卡特兰数主要有以下几个用途：

1.不同的出栈入栈数；

2.n个点组成的不同的二叉树的数目；

3.凸多边形的三角剖分划分；

4.括号化问题；

通项公式是：h(n) = C(2n-2,n-1)/n，n=1,2,3,...

递推公式：h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2

这个题就是第一种情况。

代码：

#include<cstdio>
#define maxn 10009
#define mod 1000000007
#define ll long long
using namespace std;

ll f[maxn];

ll katelant(int n)
{
    if(n==2)return 1;
    if(n==3)return 1;
    for(int i=2; i<n; i++)
    {
        if(f[i]==0)f[i]=katelant(i)%mod;
        if(f[n-i+1]==0)f[n-i+1]=katelant(n-i+1)%mod;
        f[n]+=(f[i]*f[n-i+1])%mod;
    }
    return f[n];
}

int main()
{
    f[2]=f[3]=1;
    katelant(10005);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld
",f[n+2]);
    }
    return 0;
}