cfgym101411E

201707 （ACM）动态规划----计数

• 一开始推出来的公式如下。

memset(f,0,sizeof(f));
f[0][0]=f[1][0]=1;
rep(i,1,n+1) {
    rep(j,1,i+1) {
        f[(j-1)&1][i]=(f[(j-1)&1][i]+1ll*f[0][j-1]*f[0][i-j]%m*C[i-1][j-1]%m)%m;
    }
}
printf("%d\n",(f[0][n]+f[1][n])%m);

• 但是n太大，肯定会MLE+TLE，所以可以优化

memset(f,0,sizeof(f));
memset(c,0,sizeof(c));
f[0]=f[1]=1;
c[0]=c[1]=1;
rep(i,2,n+1) {
    for(int j=1;j<=i;j+=2) {
        f[i]=(f[i]+1ll*f[j-1]*f[i-j]%m*c[j-1]%m)%m;
    }
    for(int j=i;j>=1;--j) {
        c[j]=(c[j]+c[j-1])%m;
    }
}
printf("%lld\n",(1ll*f[n]*(1+(1<n)))%m);