题意
对于一个长度为 \(n\) 的仅由 \(N,O,I\) 组成且不包含字串 \(NOI\) 的字符串 \(S\)，其与一个给定的长度为 \(K\) 的字符串的最长公共子序列为 \(LCS\)。
求出对于 \(LCS=0 \sim K\)，一共有多少种合法的字符串 \(S\)。
\(n \leq 1000,K \leq 15\)。
思路
对于朴素的 \(\mathrm{LCS}\)，有一种很经典的动态规划做法，设 \(g_{i,j}\) 为第一个字符串中长度为 \(i\) 的前缀与第二个字符串中长度为 \(j\) 的前缀的 \(\mathrm{LCS}\)，得到转移方程：
\[g_{i,j}=\max(g_{i-1,j},g_{i,j-1},g_{i-1,j-1}+[A_i=B_j]) \]对于本题来说，还要求构造的字符串中不含有字串 \(NOI\)，那么一种很直观的想法就是设 \(f_{i,g_{i,k},len}\) 前 \(i\) 个字符与给定字符串的最长公共子序列为 \(g_{i,k}\)，且当前字符串的后缀匹配到字符串 \(NOI\) 的第 \(len\) 位的方案数。
对于这种外层 dp 的状态为内层 dp 的结果的转移方式，就被称为 dp 套 dp。
在转移的时候，根据 \(g_{i,j}\) 的转移方程，需要用到 \(j=0 \sim {k-1}\) 的所有 \(g_{i,j}\)。那么肯定不可能直接将数组放在转移状态中，注意到 \(K\) 的取值实际上也很小，可以用一个二进制数来代表 \(g_{i,j}\) 的状态，只需要令这个二进制数的第 \(i\) 位表示当前位置是否成功匹配即可（也可以看出是 \(g_{i,j}\) 的差分数组），在逆向生成 \(g\) 数组的时候只需要做一遍前缀和即可。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,M=17,mod=1e9+7;
int f[2][1<<M][3],g[2][N],n,m,ans[N];char s[N];
void Add(int &a,int b){a+=b;((a>=mod)&&(a-=mod));}
void decode(int S)
{
for(int i=1;i<=m;i++) g[0][i]=(S>>i-1)&1;
for(int i=1;i<=m;i++) g[0][i]+=g[0][i-1];
}
int encode()
{
int S=0;for(int i=1;i<=m;i++) if(g[1][i]>g[1][i-1]) S|=1<<i-1;return S;
}
int count(int S){int res=0;while(S) res++,S-=S&-S;return res;}
void update(int nex,int S,int l,char c,int w)
{
decode(S);
for(int i=1;i<=m;i++)
{
g[1][i]=max(g[1][i-1],g[0][i]);
if(c==s[i]) g[1][i]=max(g[1][i],g[0][i-1]+1);
}
S=encode();Add(f[nex][S][l],w);
}
int main()
{
scanf("%d%d",&n,&m);scanf("%s",s+1);f[0][0][0]=1;
for(int i=0;i<n;i++)
{
int now=i&1,nex=i+1&1;memset(f[nex],0,sizeof(f[nex]));
for(int j=0;j<(1<<m);j++)
{
if(f[now][j][0])
{
update(nex,j,1,'N',f[now][j][0]);
update(nex,j,0,'O',f[now][j][0]);
update(nex,j,0,'I',f[now][j][0]);
}
if(f[now][j][1])
{
update(nex,j,2,'O',f[now][j][1]);
update(nex,j,1,'N',f[now][j][1]);
update(nex,j,0,'I',f[now][j][1]);
}
if(f[now][j][2])
{
update(nex,j,1,'N',f[now][j][2]);
update(nex,j,0,'O',f[now][j][2]);
}
}
}
for(int i=0;i<(1<<m);i++) for(int j=0;j<3;j++) Add(ans[count(i)],f[n&1][i][j]);
for(int i=0;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
/*
3 2
NO
*/