UOJ Logo Universal Online Judge

UOJ

#782. 新年的搜索记录

附件下载 统计

由于粉免和兔子是不可区分的,粉免可以在粉兔的队伍中跑来跑去。更可怕的是,免子是一种量子生物,它们的质量是测不准的!这严重干扰了你的计划。

幸运的是,你想起粉兔经常在网上搜索一些有关自己大作业的事情,而粉免则只会上 arXiv。聪明的你想起可以用这一点来区分。

具体来说,对于一个搜索内容,我们用字符串 $S$ 来表示它。令 $g(S)$ 为字典序比较意义下 $S$ 的最大后缀。当粉兔认为自己的搜索内容不合适的时候,就会令 $S$ 变为 $S$ 拼接上 $g(S)$ 形成的字符串,表示对 $S$ 中重要的部分进行强调,然后再搜一次。粉兔会重复这一搜索过程,直到满意为止。

如果一只兔子(免子)是粉兔的话,它应该对这样的搜索方式非常熟练,那么数出一条搜索记录中每种字符的出现次数也不再话下。

由于你只是一只拥有计算机的跳蚤,你当然需要写一个程序来确保粉兔给出的答案是对的:假设粉兔对搜索内容连续进行了 $k$ 次强调,那么你要给出每种字符在最后的搜索记录中出现了几次。由于这个次数太大,需要对 $998244353$ 取模。

形式化题意:

对一个字符串 $S$ 定义操作 $f(S)=S+g(S)$,其中 $+$ 为字符串拼接,$g(S)$ 为字典序比较意义下 $S$ 的最大后缀。

求 $f^k(S)$ 中每种字符的出现次数对 $998244353$ 取模,其中 $f^k(S)=f(f^{k-1}(S)),f^0(S)=S$。

输入格式:

第一行,一个仅包含小写字母的字符串 $S$。

第二行,一个整数 $k$。

输出格式:

一行,共 $26$ 个整数 $c_a,\ldots,c_z$,按字母表顺序表示每种小写字母出现次数模 $998244353$。

样例一

input

aacbc
2

output

2 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

explanation

$S=\texttt{aacbc},\ f(S)=\texttt{aacbccbc},\ f^2(S)=f(f(S))=\texttt{aacbccbcccbc}$。

样例二

见附件下载。该样例满足子任务 2 的限制。

样例三

见附件下载。该样例满足子任务 3 的限制。

样例四

见附件下载。该样例满足子任务 5 的限制。

数据范围:

对于 $100\%$ 的数据:$1\leq |S|\leq 6\times 10^5,\ 1\leq k\leq 10^9$,字符串 $S$ 仅包含小写字母。

子任务编号 $\lvert S \rvert \leq $ $k \leq $ 分值
$1$ $2 \times 10^5$ $1$ $20$
$2$ $100$ $8$ $20$
$3$ $2\,000$ $10^9$ $20$
$4$ $2 \times 10^5$ $20$
$5$ $6 \times 10^5$ $20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$