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;
}