分数: 600 点
问题陈述
给你一个小写英文字符串 S 长度 N 和一个整数 M。对于每个 k=0,1,\ldots,N,解决以下问题:
- 有 26^M 长度为小写英文字符串 M。其中,求数,取模 998244353,其最长公共子序列为 S 的长度正好 k.
约束
- 1\leq N\leq 10
- 1\leq M\leq 100
- N 和 M 是整数。
- S 是长度为小写英文字符串 N.
输入
输入由标准输入按以下格式给出:
N M S
输出
让 \mathrm{ans}_i 是以下问题的答案 k=i。按以下格式打印答案:
\mathrm{ans}_0 \mathrm{ans}_1 \ldots \mathrm{ans}_N
示例输入 1
2 2 ab
示例输出 1
576 99 1
的答案 k=0,1,2 如下:
- 对于 k=0: 长度之中 2 小写英文字符串,具有最长公共子序列的长度 0 与
ab包括字符串,例如cd,re,zz,总计 576. - 对于 k=1: 长度之中 2 小写英文字符串,具有最长公共子序列的长度 1 与
ab包括字符串,例如ac,wa,ba,总计 99. - 对于 k=2: 长度之中 2 小写英文字符串,有 1 字符串 (
ab) 的最长公共子序列ab有长度 2.
示例输入 2
3 4 aaa
示例输出 2
390625 62500 3750 101
示例输入 3
7 50 atcoder
示例输出 3
309810541 226923474 392073062 146769908 221445233 435648037 862664208 238437587