P10202 [湖北省选模拟 2024] 沉玉谷 Solution

好像比题解劣一个 \(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";
}