题意
给出一个长度为 \(k\) 的字符串，其中只含有 \(N,O,I\) 三种字符。
对于所有 \(i\in[1,n]\)，求出长度为 \(n\)，只含有 \(N,O,I\) 三种字符，不存在字串 \(NOI\)，与给出串的最长公共子序列长度为 \(i\) 的字符串数。\(\pmod{10^9+7}\)。
\(k\le15,n\le1000\)。
思路
先来思考最长公共子序列的转移 \(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[a_i=n_j])\)，其中中括号是艾弗森括号。
考虑把最长公共子序列的 \(dp\) 数组塞进另一个 \(dp\) 里，即设状态 \(F_{i,f,l}\) 表示前 \(i\) 位和给出字符串的前 \(j\) 位最长公共子序列的长度是 \(f_j\)，和字符串 \(NOI\) 匹配到第 \(l\) 位的方案数，转移时直接枚举下一个字符，然后再跑一遍 \(dp\) 更新 \(f\)。但是这样肯定是会炸掉的。发现 \(f\) 的相邻两位相差之多为 \(1\)，做个差分就变成 \(01\) 串了。
代码
// Problem: P4590 [TJOI2018] 游园会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4590
// Memory Limit: 250 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{int z;Modint(){z=0;}Modint(int x){x%=mod;z=x<0?x+mod:x;}Modint(long long x){x%=mod;z=x<0?x+mod:x;}Modint(short x){x%=mod;z=x<0?x+mod:x;}Modint(char x){x%=mod;z=x<0?x+mod:x;}Modint(bool x){x%=mod;z=x<0?x+mod:x;}friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}Modint operator-()const{return (Modint){-z};}Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}Modint&operator++(){z++,z%=mod;return *this;}Modint&operator--(){z--,z%=mod;return *this;}Modint operator++(int){Modint ls=*this;z++,z%=mod;return ls;}Modint operator--(int){Modint ls=*this;z--,z%=mod;return ls;}friend Modint ksm(Modint a,int b){Modint ans=1;while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}return ans;}friend void read(Modint&z){int x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();f?x=-x:0;z.z=x;}friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int maxn=1010,maxk=20,mod=1000000007,maxzt=65540;
#define M Modint<mod>
int n,k,ff[maxk],fff[maxk];
M f[2][maxzt][5],ans[maxk];
char c[maxn];
void get_nxt(int i,int s,int l,int&nxt_s,int&nxt_l,char x){if(l==0){if(x=='N') nxt_l=1;else nxt_l=0;}if(l==1){if(x=='O') nxt_l=2;else if(x=='N') nxt_l=1;else nxt_l=0;}if(l==2){if(x=='I'){nxt_l=-1;return ;}else if(x=='N') nxt_l=1;else nxt_l=0;}for(int i=0;i<k;i++) ff[i+1]=ff[i]+!!(s&(1<<i));for(int i=1;i<=k;i++) fff[i]=max({fff[i-1],ff[i],ff[i-1]+(x==c[i])});nxt_s=0;for(int i=1;i<=k;i++) if(fff[i]-fff[i-1]) nxt_s^=(1<<(i-1));
}
signed main(){read(n,k);for(int i=1;i<=k;i++) read(c[i]);f[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<(1<<k);j++) for(int l=0;l<3;l++){int nxt_j,nxt_l;if(!f[i&1][j][l].z) continue;get_nxt(i,j,l,nxt_j,nxt_l,'N');if(~nxt_l) f[i+1&1][nxt_j][nxt_l]+=f[i&1][j][l];get_nxt(i,j,l,nxt_j,nxt_l,'O');if(~nxt_l) f[i+1&1][nxt_j][nxt_l]+=f[i&1][j][l];get_nxt(i,j,l,nxt_j,nxt_l,'I');if(~nxt_l) f[i+1&1][nxt_j][nxt_l]+=f[i&1][j][l];}memset(f[i&1],0,sizeof(f[i&1]));}for(int i=0;i<(1<<k);i++){int cnt=0;for(int j=0;j<k;j++) cnt+=!!(i&(1<<j));ans[cnt]+=f[n&1][i][0]+f[n&1][i][1]+f[n&1][i][2];}for(int i=0;i<=k;i++) write(ans[i]),write("\n");return 0;
}