P10202 Solution

cnyzz · 2024-02-28 14:23:46 · 题解

好像比题解劣一个 n，但是也跑的很快。

首先说明，问题等价于计算有多少种本质不同的方案使得整个序列被删完，证明省略。

考虑用区间的方式表述这些操作，具体的，忽略删除后的移位操作，将每次删除的左右段点视为一个区间，则一定会有：

• 区间的并是 [1,n]。
• 区间之间要么不交，要么包含。
• 对于每一个区间，没被其内部的区间包含的点一定会与该区间操作的颜色相同。

于是尝试 DP，令 f_{l,r,k} 表示 [l,r] 内的覆盖方案个数，要求包含 [l,r]，同时需要步数是 k 步，g_{l,r,k,v} 表示 [l,r] 内的一组覆盖方案，不要求包含完 [l,r]，但是要求只能剩下至多一种数，且这种数是 v，同时需要步数是 k 步。
容易枚举最右侧的区间来转移，算贡献需要使用组合数，于是可以做到 O(n^6)。

const int N=55;
int a[N];
modint f[N][N][N],g[N][N][N][N],C[N][N];
void solve() {
    int n=read();
    FOR(i,1,n) a[i]=read();
    C[0][0]=1;
    FOR(i,1,n) { C[i][0]=1; FOR(j,1,i) C[i][j]=C[i-1][j]+C[i-1][j-1]; }
    FOR(i,1,n) f[i][i][1]=1,g[i][i][1][0]=1,g[i][i][0][a[i]]=1,g[i][i-1][0][0]=1;
    FOR(len,2,n) FOR(l,1,n-len+1) {
        int r=l+len-1;
        FOR(i1,0,r-l) g[l][r][i1][a[l]]+=g[l+1][r][i1][0]+g[l+1][r][i1][a[l]];
        // FOR(i1,0,r-l) g[l][r][i1][a[r]]+=g[l][r-1][i1][0]+g[l][r-1][i1][a[r]];
        FOR(x,l,r-1) if(a[x]==a[l])
            FOR(i1,0,x-l+1) FOR(i2,0,r-x) FOR(k,0,n)
                g[l][r][i1+i2][k]+=f[l][x][i1]*g[x+1][r][i2][k]*C[i1+i2][i1];
        if(a[l]==a[r])
            FOR(i1,0,r-l-1) {
                modint tp=g[l+1][r-1][i1][a[l]]+g[l+1][r-1][i1][0];
                g[l][r][i1+1][0]+=tp,f[l][r][i1+1]+=tp;
            }
    }
    modint o=0;
    FOR(i,1,n) o+=g[1][n][i][0];
    cout<<o.x<<"\n";
}