LINK：游园会
容易想到 设(f[i][j][k][l])前i个字符 j表示状压的w个字符状态为j 长度<=k 匹配到了NOI的第l个位置的方案数.
不过只能得到30分。
考虑优化 其实优化就只能优化如何快速得到LCS 这个问题 (3^15cdot 15)的状态量无法很难接受。
考虑降低这个状态量。考虑如果在一个自动机上 那么我们这个状态就可以表示匹配到了自动机上某个节点。
不过最长公共子序列自动机 并不存在。
考虑人为构造这个东西 考虑求两个串的最长公共子序列的dp.
(dp_{i,j})表示A串前i个字符B串前j个字符的最大长度.
容易得到转移:(dp_{i,j}=max(dp_{i-1,j},dp{i,j-1},dp_{i-1,j-1}+[A_i==B_j]))
那么其实只要知道(dp_i-1)这个数组和当前这个字符(A_i)就可以推向下一个字符。
进一步的 以(dp_i)为最长公共子序列的节点 那么每次转移只需要枚举下一个字符是谁 就可以很容易的重新得到新的LCS的状态和长度.
这样就可以把上述的那么大的状态量压缩成了这样的dp数组 不过直接存一个数组是需要hash的。
可以观察得到 (dp_i)是不降的 可以将其差分就得到了一个二进制串 最终状态量为(2^w) 可以通过此题.
const int MAXN=1010,maxn=35010;
int n,k,u,maxx;
int f[2][maxn][3];
char a[MAXN];
int g[2][MAXN],sum[maxn],ans[MAXN];
inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void jy(int s)
{
rep(1,k,i)g[0][i]=s>>i-1&1;
rep(1,k,i)g[0][i]+=g[0][i-1];
}
inline int ys()
{
int S=0;
rep(1,k,i)if(g[1][i]-g[1][i-1])S|=1<<(i-1);
return S;
}
inline void update(int s,int l,char c,int w)
{
jy(s);
rep(1,k,i)
{
g[1][i]=max(g[0][i],g[1][i-1]);
if(c==a[i])g[1][i]=max(g[1][i],g[0][i-1]+1);
}
int j=ys();add(f[u][j][l],w);
}
int main()
{
freopen("1.in","r",stdin);
gt(n);gt(k);gc(a);
maxx=1<<k;--maxx;
f[u][0][0]=1;
rep(1,n,i)
{
u=u^1;
rep(0,maxx,j)rep(0,2,k)f[u][j][k]=0;
rep(0,maxx,j)
{
if(f[u^1][j][0])
{
update(j,1,'N',f[u^1][j][0]);
update(j,0,'O',f[u^1][j][0]);
update(j,0,'I',f[u^1][j][0]);
}
if(f[u^1][j][1])
{
update(j,1,'N',f[u^1][j][1]);
update(j,2,'O',f[u^1][j][1]);
update(j,0,'I',f[u^1][j][1]);
}
if(f[u^1][j][2])
{
update(j,1,'N',f[u^1][j][2]);
update(j,0,'O',f[u^1][j][2]);
}
}
}
rep(0,maxx,i)
{
sum[i]=sum[i>>1]+(i&1);
rep(0,2,j)add(ans[sum[i]],f[u][i][j]);
}
rep(0,k,i)put(ans[i]);
return 0;
}