DP 套 DP 还是蛮有趣的（
可以先不考虑不含 \(\texttt{NOI}\) 子串的限制。（这时其实是个丽洁姐的原题）
注意到 LCS 不太方便用状态表示，于是可以考虑造一个 LCS 自动机。
考虑传统的 \(O(|A||B|)\) 求串 \(A,B\) LCS 的 DP 方法： \[ f_{i,j} = \max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1} + [A_i = B_j]\} \]
注意到这个 DP 仅涉及到两个串的上一个字符，并且此题中有一个串是固定的，那么可以把另一个串对应的维度看做一个自动机上的结点。
麻烦的是，空间会很大，而且难以得出结点数的上界。
再次考虑 \(f\) 的定义，容易发现数组 \(f_i\) 的差分数组一定非 \(0\) 即 \(1\)，所以可以考虑状压（\(K \le 15\)）。
这样就会得到一个比较松但是足够用的上界，即 \(2^{15}\)。
（经实测本题数据中最多的结点数不超过 \(5000\)）
然后 BFS 建自动机即可。
解决了自动机的问题之后，考虑设 \(g_{i,j}\) 表示兑奖串的前 \(i\) 位能走到自动机上的结点 \(j\) 的方案数。
那么转移时仅需要枚举新的字符并走后缀自动机上的边即可。
然后涉及到不含 \(\texttt{NOI}\) 子串的限制。
——实际上也很简单，只需要新增一维表示当前后缀和 \(\texttt{NOI}\) 的最长匹配长度。
此外，由于此题时限较宽裕，所以也可以不显式建出自动机而是在转移 \(g\) 时直接转移 \(f\)。
（这样就要按照状压的方式来存储结点）
然后这其实就是 DP 套 DP 的名字来源（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
const int N = 1e3;
const int K = 15;
const int M = 5e3;
const int mod = 1e9 + 7;
int n,k,s[K + 5];
inline int trans(int w,int c)
{
static int a[K + 5],f[K + 5];
int ret = 0;
for(register int i = 1;i <= k;++i)
a[i] = a[i - 1] + ((w >> i - 1) & 1);
for(register int i = 1;i <= k;++i)
f[i] = max(max(a[i],f[i - 1]),a[i - 1] + (s[i] == c)),
ret |= f[i] - f[i - 1] << i - 1;
return ret;
}
int q[M + 5];
int head,tail;
int tot,e[M + 5][3],id[(1 << K) + 5],rk[(1 << K) + 5];
inline void bfs()
{
rk[id[q[++tail] = 0] = ++tot] = 0;
for(register int p,dir,x;head < tail;)
{
p = q[++head],x = id[p];
for(register int i = 0;i < 3;++i)
{
dir = trans(p,i);
if(id[dir])
e[x][i] = id[dir];
else
rk[e[x][i] = id[dir] = ++tot] = q[++tail] = dir;
}
}
}
int f[2][M + 5][3],ans[K + 5];
int main()
{
scanf("%d%d",&n,&k);
char ch;
for(register int i = 1;i <= k;++i)
scanf(" %c",&ch),s[i] = ch == 'I' ? 2 : ch == 'O';
bfs(),f[0][1][0] = 1;
for(register int i = 0;i < n;++i)
{
memset(f[(i & 1) ^ 1],0,sizeof f[(i & 1) ^ 1]);
for(register int j = 1;j <= tot;++j)
{
if(f[i & 1][j][0])
f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][0]) % mod,
f[(i & 1) ^ 1][e[j][1]][0] = (f[(i & 1) ^ 1][e[j][1]][0] + f[i & 1][j][0]) % mod,
f[(i & 1) ^ 1][e[j][2]][0] = (f[(i & 1) ^ 1][e[j][2]][0] + f[i & 1][j][0]) % mod;
if(f[i & 1][j][1])
f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][1]) % mod,
f[(i & 1) ^ 1][e[j][1]][2] = (f[(i & 1) ^ 1][e[j][1]][2] + f[i & 1][j][1]) % mod,
f[(i & 1) ^ 1][e[j][2]][0] = (f[(i & 1) ^ 1][e[j][2]][0] + f[i & 1][j][1]) % mod;
if(f[i & 1][j][2])
f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][2]) % mod,
f[(i & 1) ^ 1][e[j][1]][0] = (f[(i & 1) ^ 1][e[j][1]][0] + f[i & 1][j][2]) % mod;
}
}
for(register int i = 1;i <= tot;++i)
for(register int j = 0;j < 3;++j)
ans[__builtin_popcount(rk[i])] = (ans[__builtin_popcount(rk[i])] + f[n & 1][i][j]) % mod;
for(register int i = 0;i <= k;++i)
printf("%d\n",ans[i]);
}