[AGC046D]Secret Passage

CLV.[AGC046D]Secret Passage

稍微观察一下就能发现，任一时刻，我们剩下的东西必然是一段定死了的后缀，加上一些可以任意塞位置的 \(0\) 与 \(1\)。考虑任意一个由上述时刻生成的串，就会发现它与该后缀的最长公共子序列长度即为后缀长度，且还剩余一些 \(0\) 与 \(1\)。

于是考虑模拟最长公共子序列的过程。设 \(g_{i,j,k}\) 表示长度为 \(n-i+1\) 的后缀，所有与其LCS就是该后缀本身，且多余 \(j\) 个 \(0\)、\(k\) 个 \(1\) 的串数。为了不重复计数，我们强制 \(0\) 只能插在原后缀的 \(1\) 前面，\(1\) 只能插在原后缀的 \(0\) 前面。倒序转移即可。

并非所有 \((i,j,k)\) 都是合法的。我们还需要求出合法的状态。设 \(f_{i,j,k}\) 表示其是否合法。则，一个状态合法，当且仅当其通过一步LCS匹配能够到达另一个合法状态，或者其通过删除再插入操作能够到达另一个合法状态。两种方案分别转移即可。

时间复杂度 \(O(n^3)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
char s[310];
int n,g[310][310][310],res,h[310][310];
bool f[310][310][310];
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	f[0][0][0]=true;
	for(int i=1;i<=n;i++){
		for(int j=n;j>=0;j--)for(int k=n;k>=0;k--){
			f[i][j][k]|=f[i-1][j][k];
			if(s[i]=='0')f[i][j][k]|=f[i][j][k+1];
			if(s[i]=='1')f[i][j][k]|=f[i][j+1][k];
		}
		if(i>1)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
			if((s[i-1]=='0'||s[i]=='0')&&j)f[i][j][k]|=f[i-2][j-1][k];
			if(s[i-1]=='0'&&s[i]=='0'&&j)f[i][j][k]|=f[i-1][j-1][k+1];
			if((s[i-1]=='1'||s[i]=='1')&&k)f[i][j][k]|=f[i-2][j][k-1];
			if(s[i-1]=='1'&&s[i]=='1'&&k)f[i][j][k]|=f[i-1][j+1][k-1];
		}
	}
	g[n][0][0]=1;
	for(int i=n;i;i--)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
		(g[i-1][j][k]+=g[i][j][k])%=mod;
		if(s[i]=='0')(g[i][j][k+1]+=g[i][j][k])%=mod;
		if(s[i]=='1')(g[i][j+1][k]+=g[i][j][k])%=mod;
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)if(f[i][j][k])(res+=g[i][j][k])%=mod;
	printf("%d\n",(res+mod-1)%mod);
	return 0;
}