CF1515E 题解

yuzhechuan · 2021-05-05 14:28:21 · 题解

类比CEOI kangaroo一题的插入思想，有一种 O(n^2) 的简单做法

令 f_{i,j} 表示已开机 i 台，构成了 j 个连续段，每段间距离是大于 1 的一个 不确定值

转移有 新建段，段扩增，段合并 共五种情况

注意由于两段间的距离是不确定的，所以怎么插都是可以的，转移系数见代码

const int N=405;
int n,f[N][N],mod;

signed main(){
    read(n);read(mod);
    f[0][0]=1;
    for(int i=0;i<n;i++) for(int j=0;j<=i;j++){
        f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(j+1))%mod; //j+1个间隔选一个插
        f[i+1][j]=(f[i+1][j]+f[i][j]*j*2)%mod; //两端贴着开
        f[i+2][j]=(f[i+2][j]+f[i][j]*j*2)%mod; //两端隔一个开
        if(j>=2){
            f[i+2][j-1]=(f[i+2][j-1]+f[i][j]*(j-1)*2)%mod; //定两段间距离为2，有正反两种开法
            f[i+3][j-1]=(f[i+3][j-1]+f[i][j]*(j-1))%mod; //定两段间距离为3，开中间那个
        }
    }
    write(f[n][1]);
}