题解劝退系列
设长的那个串是Ａ，短的那个串是Ｂ。
那我们在如果已经知道某个Ａ的时候，Ａ[1..i]和Ｂ[1..j]的最长公共子序列$f[i][j]=max\{f[i-1][j],f[i][j-1],f[i-1][j-1]+(A[i]==B[i])\}$
于是可以递推来枚举A，顺手把NOI的情况判掉。但这复杂度显然过不了。
注意到在推的时候，每新加一个字符，就可以由f[i-1]推出f[i]，也就是说，我们根本不用记递推出来的这个A具体是什么，只要记住这个f[i]就可以了。
怎么记呢？注意到f[i][j]只能等于f[i][j-1]或者f[i][j-1]+1，也就是说，我们可以先差分这个f[i]，然后状压就能记下来了。
设trans[s][k]表示原本f数组状态是s、新加了一个k字符，转移到的状态
那么可以得到递推式$g[i+1][trans[s][k]]=\sum{g[i][s]}$,g[N][s]就是最后状态s的情况数，只要统计一下s中1的个数，记到答案里就行了。
然而还要判NOI
其实很简单，只要给g多记一维，用来表示现在这个状态已经匹配到了NOI的几位就可以了
（0,1,2通过"N"转移到1;1通过“O”转移到2;2通过“I”转移到3（这个情况不合法））
要开滚动数组
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<ctime>
#include<set>
#define pa pair<int,int>
#define lowb(x) ((x)&(-(x)))
#define REP(i,n0,n) for(i=n0;i<=n;i++)
#define PER(i,n0,n) for(i=n;i>=n0;i--)
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
#define CLR(a,x) memset(a,x,sizeof(a))
#define rei register int
using namespace std;
const int maxn=,maxk=,maxs=,p=1e9+;
typedef long long ll; ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,K,M;
int wd[maxk],ans[maxk],ne[][];
int f[][maxs][],trans[maxs][],cnt[maxs]; inline void modadd(int &x,int y){x=(x+y)%p;} int main(){
//freopen(".in","r",stdin);
rei i,j,k,l;
N=rd(),K=rd();M=<<K;
i=;while(i<K){
char c=getchar();
if(c=='N') wd[++i]=;
else if(c=='O') wd[++i]=;
else if(c=='I') wd[++i]=;
}
REP(i,,M-){
REP(j,,){
int s=,sum=,lst=,now=;
REP(k,,K){
if(wd[k]==j) now=sum+;
if(i&(<<(k-))) sum++;
if(wd[k]!=j) now=sum;
s+=(now>lst)<<(k-);lst=MAX(lst,now);
}trans[i][j]=s;cnt[i]=sum;
//printf("%d %d %d %d\n",i,j,s,sum);
}
}
ne[][]=;ne[][]=ne[][]=ne[][]=;
bool b=;f[][][]=;
REP(i,,N-){
//memcpy(f[b],f[b^1],sizeof(f[b]));
CLR(f[b^],);
REP(j,,M-){
REP(l,,){if(!f[b][j][l]) continue;
REP(k,,){
if(l==&&k==) continue;
modadd(f[b^][trans[j][k]][ne[l][k]],f[b][j][l]);
//printf("f[%d][%d][%d]=%d -%d> ",i,j,l,f[b][j][l],k);
// printf("f[%d][%d][%d]=%d\n",i+1,trans[j][k],ne[l][k],f[b^1][trans[j][k]][ne[l][k]]);
}
}
}b^=;
}
REP(i,,M-){
REP(j,,)
modadd(ans[cnt[i]],f[b][i][j]);
}REP(i,,K) printf("%d\n",ans[i]);
return ;
}