hdu 2811 即老菜鸟杯 1003

比赛最后才和同学一起AC的一道题目...
f(n)=sum(C(n-1,j)*f(j)*f(n-1-j),0<=j<=(n-1)/2) 当然 n-1=2*j的时候组合数必须除以2.
这个时候还得考虑是否会越界..所以有个%k的处理

#include<stdio.h>

__int64 mmg[1005],n,k;

__int64 C[1005][1000],flag[1005][1000];

int main()

{

int i,j;

while(scanf("%I64d%I64d",&n,&k)!=EOF)

{

C[1][0]=C[1][1]=1%k;

flag[1][0]=flag[1][1]=(1/k)%2;

for(i=2;i<=n;i++)

{

C[i][0]=C[i][i]=1%k;

flag[i][0]=flag[i][i]=(1/k)%2;

for(j=1;j<i;j++)

{

C[i][j]=(C[i-1][j]+C[i-1][j-1])%k;

flag[i][j]=flag[i-1][j]+flag[i-1][j-1]+(C[i-1][j]+C[i-1][j-1])/k;

flag[i][j]=flag[i][j]%2;

}

mmg[1]=1%k;

mmg[2]=1%k;

for(i=3;i<=n;i++)

{

mmg[i]=mmg[i-1];

for(j=1;j<=(i-1)/2;j++)

{

if(i-1==2*j)

{

if(flag[i-1][j]==1)

mmg[i]+=(((mmg[j]%k)*(mmg[i-j-1]%k))%k)*(((C[i-1][j]+k)/2)%k);

else

mmg[i]+=(((mmg[j]%k)*(mmg[i-j-1]%k))%k)*(((C[i-1][j])/2)%k);

}

else

mmg[i]+=(((mmg[j]%k)*(mmg[i-j-1]%k))%k)*(C[i-1][j]%k);

mmg[i]=mmg[i]%k;

}

printf("%I64d\n",mmg[n]);

}

posted on 2009-05-02 20:42 米游阅读(350) 评论(0) 编辑收藏引用所属分类: ACM

常用链接

留言簿(1)

随笔分类

随笔档案

ACM大牛

计算机图形学

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: 有道难题... zoj 3211 Dream City 09.5.23 退役感言 RMQ ST算法 (区间最大(最小)值问题) 使用后缀数组解决zoj 3199 Longest Repeated Substring 线段树求矩形覆盖的周长 pku 1177 hdu 2816 即老菜鸟杯的1008题目 hdu 2813 即老菜鸟杯 1005题 hdu 2812 即老菜鸟杯 1004 hdu 2811 即老菜鸟杯 1003

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理