一个卡特兰数的应用;
卡特兰数主要有以下几个用途:
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==)return ;
if(n==)return ;
for(int i=; i<n; i++)
{
if(f[i]==)f[i]=katelant(i)%mod;
if(f[n-i+]==)f[n-i+]=katelant(n-i+)%mod;
f[n]+=(f[i]*f[n-i+])%mod;
}
return f[n];
} int main()
{
f[]=f[]=;
katelant();
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%lld\n",f[n+]);
}
return ;
}