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==)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 ;
}
上一篇:APP IM 之 XMPP和Jabber及选择方案


下一篇:storm从入门到放弃(二),任务分配过程-核心机密