G - 随机学生ID

得分: $600$ 分

问题描述

高桥小学有 $N$ 个新学生。对于 $i = 1, 2, \ldots, N$，第 $i$ 个新学生的名字是 $S_i$ （由小写英文字母组成的字符串）。 这 $N$ 个新学生的名字两两不同。

给这 $N$ 个学生分配学生ID为 $1, 2, 3, \ldots, N$，按照他们的名字按字典序 升序来排。但是，我们使用以下顺序而不是小写英文字母的普通顺序，其中 a 是最小的，z 是最大的：

• 首先，高桥校长从长度为26的字符串 abcdefghijklmnopqrstuvwxyz 的 $26!$ 个排列中均匀随机地选择一个字符串 $P$。
• 在 $P$ 中较早出现的小写英文字母被认为是较小的字符。

对于每个 $N$ 个学生，求分配的学生ID的期望值，模 $998244353$（详见备注）。

备注

我们可以证明所求的期望值总是一个有理数。而且，在此问题的约束条件下，当该值用两个互质整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$时，我们可以证明存在一个唯一的整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 并且 $0 \leq R \lt 998244353$。找到这个 $R$。

约束

• $2 \leq N$
• $N$ 是整数。
• $S_i$ 是长度至少为 $1$ 的由小写英文字母组成的字符串。
• 给定字符串的长度之和至多为 $5 \times 10^5$。
• $i \neq j \Rightarrow S_i \neq S_j$

输入

从标准输入中按以下格式给出：

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

输出

打印 $N$ 行。 对于每个 $i = 1, 2, \ldots, N$，第 $i$ 行应该包含分配给第 $i$ 个学生的学生ID的期望值，模 $998244353$。

3
a
aa
ab

1
499122179
499122179

分配给学生 $1$ 的学生ID的期望值为 $1$；分配给学生 $2$ 和 $3$ 的学生ID的期望值为 $\frac{5}{2}$。

注意，答案应该打印为模 $998244353$ 的形式。 例如，学生 $2$ 和 $3$ 的学生ID的期望值为 $\frac{5}{2}$， 而我们有 $2 \times 499122179 \equiv 5\pmod{998244353}$， 因此应该打印 $499122179$。

3
a
aa
aaa

1
2
3

分配给学生 $1$ 的学生ID的期望值为 $1$；分配给学生 $2$ 的学生ID的期望值为 $2$；分配给学生 $3$ 的学生ID的期望值为 $3$。