随笔-38  评论-23  文章-0  trackbacks-0
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 米游 阅读(361) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 米游