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;
const int N=310; 
int n,res,g[N][N][N],h[N][N];
bool f[N][N][N];
char s[N];
signed main(){
    scanf("%s",s+1);
	n=strlen(s+1);
    f[0][0][0]=1;
    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",(res+mod-1)%mod);
    return 0;
}