F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5336. -- [TJOI2018]party

5336: [TJOI2018]party

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 137  Solved: 96
[Submit][Status][Discuss]

Description

小豆参加了NOI的游园会,会场上每完成一个项目就会获得一个奖章,奖章  只会是N, O, I的字样。在会场上他收集到了K个奖章组成的串。
兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。
现在已知兑奖串长度为N,并且在兑奖串上不会出现连续三个奖章为NOI,即奖章中不会出现子串NOI。
现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

Input

第一行两个数,N,K分别代表兑奖串的长度,小豆收集的奖章串的长度。
第二行一共K个字符,表示小豆得到奖章串。
N<=1000 & K<=15

Output

一共K+1行,第i行表示小豆最后奖励等级为i-1的不同的合法兑奖串的个数,可能这个数会很大,结果对10^9 + 7取模。

Sample Input

3 2
NO

Sample Output

1
19
6
提示
最长公共子序列长度0的串有:III;
最长公共子序列长度2的串有:NON, NNO, NOO, ONO,
INO, NIO;
除去NOI,余下的19(26-6-1)种为最长公共子序列长度为1。

HINT

Source

[Submit][Status][Discuss]

HOME Back