題意：
求長度為N的zig-zag序列數(shù)
做法：
設(shè)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