AtCoder Beginner Contest 391
翻译中…
Problem Statement
翻译中…
You are given a lowercase English string $S$ of length $N$ and an integer $M$. For each $k=0,1,\ldots,N$, solve the following problem:
翻译中…
- There are
$26^M$lowercase English strings of length$M$. Among these, find the number, modulo$998244353$, of strings whose longest common subsequence with$S$has length exactly$k$.
翻译中…
Constraints
翻译中…
$1\leq N\leq 10$$1\leq M\leq 100$$N$and$M$are integers.$S$is a lowercase English string of length$N$.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N M
S翻译中…
Output
翻译中…
Let $\mathrm{ans}_i$ be the answer for $k=i$. Print the answers in the following format:
翻译中…
\mathrm{ans}_0 \mathrm{ans}_1 \ldots \mathrm{ans}_N翻译中…
样例
Input #1
2 2
ab
Output #1
576 99 1
The answers for $k=0,1,2$ are as follows:
- For $k=0$: Among length $2$ lowercase English strings, those with a longest common subsequence of length $0$ with `ab` include strings such as `cd`, `re`, `zz`, totaling $576$.
- For $k=1$: Among length $2$ lowercase English strings, those with a longest common subsequence of length $1$ with `ab` include strings such as `ac`, `wa`, `ba`, totaling $99$.
- For $k=2$: Among length $2$ lowercase English strings, there is $1$ string (`ab`) whose longest common subsequence with `ab` has length $2$.
Input #2
3 4
aaa
Output #2
390625 62500 3750 101
Input #3
7 50
atcoder
Output #3
309810541 226923474 392073062 146769908 221445233 435648037 862664208 238437587
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。