游园会
考虑直接设 \(F(i,j)\) 表示对于兑奖串前 \(i\) 位匹配奖章串的 \(\mathrm{LCS}\) 位 \(j\) 的方案数，但是发现没有办法直接转移，因为对于匹配到奖章串不同位置新加一个字符情况是不一样的。
考虑 \(\mathrm{LCS}\) 的转移，设 \(dp(i,j)\) 表示兑奖串前 \(i\) 位与奖章串前 \(j\) 位的 \(\mathrm{LCS}\) 的长度，那么有转移
\[dp(i,j)=max\{ dp(i-1,j),dp(i,j-1),dp(i-1,j-1)+[A_i=b_j]\} \]发现转移只跟 \(dp(i-1)\) 的状态相关，因为位数很小，所以我们考虑讲某个状态与奖章串的前 \(i\) 位的 \(\mathrm{LCS}\) ，设为 \(f_i\) 发现 \(\mathrm{LCS}\) 单增且增量为 \(1\)，那么直接可以压成 \(\mathrm{01}\) 串。
那么内层 \(\mathrm{dp}\) 是一个匹配状态加一个字符会转移到的状态（求出值是什么），那么外层 \(\mathrm{dp}\) 是一个计数。
设 \(F(i,s)\) 表示到兑奖串前 \(i\) 位匹配状态为 \(s\) 的方案数，我们可以先预处理出来转移的指针 \(trans(s,c)\)，此过程与 \(\mathrm{LCS}\) 的转移类似，然后就有转移，可以滚动
\[F(i,trans(s,c)) \leftarrow F(i-1,s) \]对于 \(noi\) 限制我们可以再加一维表示匹配到第几个。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1005;
const int E=32780;
char S[N];
int trans[E][3],f[20],g[20];
int dp[3][E][5];
int ans[N],Popcount[E];
int rk[N];
int n,k,t;
void build(){
t=(1ll<<k);
for(int s=0;s<t;s++){
for(int i=1;i<=k;i++) f[i]=((s>>(i-1))&1);
for(int i=1;i<=k;i++) f[i]=f[i-1]+f[i];
for(int c=0;c<=2;c++){
for(int i=1;i<=k;i++) g[i]=f[i];
for(int i=1;i<=k;i++) g[i]=max({g[i],f[i-1]+(rk[S[i]]==c),g[i-1]});
int res=0;
for(int i=1;i<=k;i++) res|=((g[i]-g[i-1])<<(i-1));
trans[s][c]=res;
}
}
}
signed main(){
scanf("%lld%lld",&n,&k);
scanf("%s",S+1);
rk['N']=0,rk['O']=1,rk['I']=2;
build();
for(int s=0;s<t;s++) Popcount[s]=Popcount[s>>1]+(s&1);
int op=0;
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int s=0;s<t;s++){
for(int c=0;c<=2;c++){
if(c==0){
dp[op^1][trans[s][c]][1]=(dp[op^1][trans[s][c]][1]+dp[op][s][0])%mod;
dp[op^1][trans[s][c]][1]=(dp[op^1][trans[s][c]][1]+dp[op][s][1])%mod;
dp[op^1][trans[s][c]][1]=(dp[op^1][trans[s][c]][1]+dp[op][s][2])%mod;
}
else if(c==1){
dp[op^1][trans[s][c]][2]=(dp[op^1][trans[s][c]][2]+dp[op][s][1])%mod;
dp[op^1][trans[s][c]][0]=(dp[op^1][trans[s][c]][0]+dp[op][s][0])%mod;
dp[op^1][trans[s][c]][0]=(dp[op^1][trans[s][c]][0]+dp[op][s][2])%mod;
}
else{
dp[op^1][trans[s][c]][0]=(dp[op^1][trans[s][c]][0]+dp[op][s][1])%mod;
dp[op^1][trans[s][c]][0]=(dp[op^1][trans[s][c]][0]+dp[op][s][0])%mod;
}
}
}
for(int s=0;s<t;s++) dp[op][s][0]=dp[op][s][1]=dp[op][s][2]=0;
op^=1;
}
for(int s=0;s<t;s++){
ans[Popcount[s]]=(ans[Popcount[s]]+dp[op][s][0]+dp[op][s][1]+dp[op][s][2])%mod;
}
for(int i=0;i<=k;i++){
printf("%lld\n",ans[i]);
}
}
优美的字符串
首先考虑如何判断一个没有 \(?\) 的字符串是否合法，我们可以设 \(f(i,0/1,0/1)\) 表示假如第 \(i\) 位字符为 \(0/1\)，前缀是否可以消成 \(0/1\)。
设 \(F(a,b,c)\) 表示这三个字符可以变成什么，考虑我们要最后字符变为 \(b\)，我们可以考虑两种合并的方式
-
一种是 \(s_{i-2},s_{i-1},s_{i}\) 合并后再与之前的合并，也就是判断 \(f(i-1,F(s_{i-2},s_{i-1},s_{i}),b)\) 是否符合。
-
另一种是将 \(i-2\) 之前的合并玩之后再进行合并，那么转移就很显然。
然后就有如下暴力
code
for(int i=3;i<=n;i+=2){
f[i][0][0] |= f[i-2][F[s[i-2]][s[i-1]][0]][0];
f[i][0][1] |= f[i-2][F[s[i-2]][s[i-1]][0]][1];
f[i][1][0] |= f[i-2][F[s[i-2]][s[i-1]][1]][0];
f[i][1][1] |= f[i-2][F[s[i-2]][s[i-1]][1]][1];
f[i][1][F[1][s[i-1]][1]] |= f[i-2][s[i-2]][1];
f[i][1][F[0][s[i-1]][1]] |= f[i-2][s[i-2]][0];
f[i][0][F[1][s[i-1]][0]] |= f[i-2][s[i-2]][1];
f[i][0][F[0][s[i-1]][0]] |= f[i-2][s[i-2]][0];
}
当我们知道 \(s_{i-1},s_{i}\) (外层 dp 枚举)，我们发现转移到 \(f(i)\) 只需要 \(f(i-2)\) （内层考虑）的状态，所以我们将 \(f(i)\) 的转态进行状压，具体就是维护五个数，分别是 \((0,1),(0,0)(1,1)(1,0),s_i\)，然后提前预处理出来转移指针，也就是 \(trans(s,a,b)\) 表示在 \(s_i\) 后面加上 \(a,b\) 两个字符后转移到的状态，所以外层转移就是
\[dp_{i+2,trans(s,a,b)} \leftarrow dp_{i,s} \]code
// ubsan: undefined
// accoders
// 优美的字符串
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e5+10;
char th[N],sh[N];
int t[N],s[N];
bool F[2][2][2];
int dp[N][50];
int trans[50][2][2];
bool las[2][2],now[2][2];
signed main(){
int T;
scanf("%lld",&T);
while(T--){
scanf("%s",th+1);
scanf("%s",sh+1);
int n=strlen(sh+1);
for(int i=1;i<=8;i++) t[i]=th[i]-'0';
for(int i=1;i<=n;i++) s[i]=sh[i]-'0';
memset(dp,0,sizeof(dp));
for(int i=0;i<8;i++){
int a=i&1;
int b=(i>>1)&1;
int c=(i>>2)&1;
F[a][b][c]=t[i+1];
}
int t=(1<<5);
for(int S=0;S<t;S++){
las[1][1]=(S>>1&1),las[1][0]=(S>>2&1),las[0][1]=(S>>3&1),las[0][0]=(S>>4&1);
int ss=(S&1);
for(int s1=0;s1<=1;s1++){
for(int s2=0;s2<=1;s2++){
now[1][1]=0,now[1][0]=0,now[0][1]=0,now[0][0]=0;
now[0][0] |= las[F[ss][s1][0]][0];
now[0][1] |= las[F[ss][s1][0]][1];
now[1][0] |= las[F[ss][s1][1]][0];
now[1][1] |= las[F[ss][s1][1]][1];
now[1][F[1][s1][1]] |= las[ss][1];
now[1][F[0][s1][1]] |= las[ss][0];
now[0][F[1][s1][0]] |= las[ss][1];
now[0][F[0][s1][0]] |= las[ss][0];
trans[S][s1][s2]=(s2&1)|(now[1][1]<<1)|(now[1][0]<<2)|(now[0][1]<<3)|(now[0][0]<<4);
}
}
}
if(s[1]!=1) dp[1][1<<4]=1;
if(s[1]!=0) dp[1][(1<<1)+1]=1;
for(int i=1;i<n;i+=2){
for(int S=0;S<t;S++){
if(s[i]==((S&1)^1)) continue;
for(int s1=0;s1<=1;s1++){
if(s[i+1]==(s1^1)) continue;
for(int s2=0;s2<=1;s2++){
if(s[i+2]==(s2^1)) continue;
dp[i+2][trans[S][s1][s2]]=(dp[i+2][trans[S][s1][s2]]+dp[i][S])%mod;
}
}
}
}
int ans=0;
for(int s=0;s<t;s++){
if(s&1){
if(s>>1&1) ans=(ans+dp[n][s])%mod;
}
else{
if(s>>3&1) ans=(ans+dp[n][s])%mod;
}
}
printf("%lld\n",ans);
}
}