Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

SDTSC 2010 goblin

题意:
求长度为N的zig-zag序列数

做法:
设Up[i][j]表示长度为i以j开头的zig序列
Down[i][j]表示长度为i以j开头的zag序列
直接递推

 1 #include <cstdio>
 2 int Up[2][4205],Down[2][4205],N,P;
 3 int main()
 4 {
 5     scanf("%d%d",&N,&P);
 6     Up[1][1]=Down[1][1]=1;
 7     for (int i=2,now=0;i<=N;++i,now^=1)
 8     {
 9         Up[now][i+1]=Down[now][0]=0;
10         for (int j=i;j;--j)
11             Up[now][j]=(Up[now][j+1]+Down[now^1][j])%P;
12         for (int j=1;j<=i;++j)
13             Down[now][j]=(Down[now][j-1]+Up[now^1][j-1])%P;
14     }
15     int ret=0;
16     for (int i=1;i<=N;++i)
17         ret=(ret+Up[N&1][i])%P;
18     printf("%d\n",(ret<<1)%P);
19     return 0;
20 }
21 


posted on 2010-05-19 14:11 jsn1993 阅读(991) 评论(0)  编辑 收藏 引用 所属分类: Math


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