我们先说一下 \(dp\) 套 \(dp\) 大概是个什么东西。
感性理解一些，你现在有一个动态规划数组 \(g\)，然后你的 \(f\) 用 \(g\) 的某种方式作为下标进行转移。
事实上，这个 \(g\) 需要满足单调性，然后相当于你是在一个 \(DAG\) 上做 \(dp\)。为什么要满足单调性，否则有可能出现环，有环代表你的状态有后效性，有后效性则无法转移。
游园会
首先最长公共子序列的动态规划是好做的，这里就不说了。
这里设最长公共子序列的动态规划数组为 \(g\)。
我们先设 \(f_{i,{w_1,w_2,\cdots,w_k}}\) 为 长度为 \(i\) 且 \(g_{i,j}=w_j\) 的字符串个数。
但是你发现 \(w\) 你存不下来。于是我们考虑有没有什么性质能够版主我们优化。
显然有 \(g_{i,j}-g_{i,j-1}\le 1\)。于是你考虑 \(f\) 的后面维度不存储真正意义上的 \(w\)，而存储 \(w\) 的差分数组，于是每一位都是 \(0\) 或者 \(1\)。状态数共 \(n\times 2^k\)，可以接受。
但是你又发现，我们知道 \(s_i\)（题目给出），也就是说当前的 \(g_i\) 只跟 \(t_i\) 和 \(g_{i-1}\) 有关。于是我们在做 \(g\) 的转移时只记 \(g_{i-1}\) 就行（就是滚动数组优化）。
然后是我们的 \(f\) 也可以用滚动数组优化，否则空间会爆。
代码：
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 40005
using namespace std;
int n,k,f[2][N][3],g[2][20],cnt[N],res[20];
char s[20];
void solve1(int state){
memset(g[0],0,sizeof g[0]);
for(int i=0;i<k;i++){
g[0][i+1]=state>>i&1;
}
for(int i=1;i<=k;i++){
g[0][i]+=g[0][i-1];
}
}
int solve2(){
int state=0;
for(int i=1;i<=k;i++){
int x=g[1][i]-g[1][i-1];
state|=x*(1<<i-1);
}
return state;
}
void solve(int cur,int state,char c,int now,int las){
if(las==0)return;//没有贡献不用转移
if(c=='I'&&now==2)return;//包含了子串NOI
int ne=c=='N'?1:0;//如果是N，下一个就从I匹配，否则从N
if(now==0&&c=='N')ne=1;//如果当前应匹配第0个且是N，后跳一位
else if(now==1&&c=='O')ne=2;//同上
solve1(state);//把差分记录的状态还原
memset(g[1],0,sizeof g[1]);//先清空
for(int i=1;i<=k;i++){
if(s[i]==c){//如果s_i=t_j，可以使用特殊转移
g[1][i]=max(g[1][i],g[0][i-1]+1);//这里的g_{0,i-1}就是lcs_{i-1,j-1}
}
g[1][i]=max({g[1][i],g[0][i],g[1][i-1]});//否则使用一般转移（g_{0,i}就是lcs_{i,j-1}，g_{1,i-1}就是lcs_{i-1,j}
}
int res=solve2();//再把当前数组弄成差分状态存进去
(f[cur][res][ne]+=las)%=mod;//继承上一个
}
signed main(){
cin>>n>>k>>s+1;
int cur=0;
f[0][0][0]=1;
for(int i=1;i<=n;i++){
cur^=1;
memset(f[cur],0,sizeof f[cur]);
for(int j=0;j<1<<k;j++){
for(int p=0;p<3;p++){
char c=p==0?'N':p==1?'O':'I';
solve(cur,j,c,0,f[cur^1][j][0]);
solve(cur,j,c,1,f[cur^1][j][1]);
solve(cur,j,c,2,f[cur^1][j][2]);
}
}
}
for(int i=1;i<1<<k;i++){
cnt[i]=cnt[i>>1]+(i&1);//cnt是这个数二进制表示有几个1，这里有几个1代表lcs长度就是几
}
for(int i=0;i<1<<k;i++){
for(int j=0;j<3;j++){
(res[cnt[i]]+=f[cur][i][j])%=mod;
}
}
for(int i=0;i<=k;i++){
cout<<res[i]<<'\n';
}
return 0;
}