← 返回题目列表

AtCoder · abc391_g

G. 许多濒海战斗舰

中文机器翻译题面 查看原题

分数: 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