分数: 600 点
问题陈述
高桥小学有 N 新生。 对于 i = 1, 2, \ldots, N,名称 i第一个新学生是 S_i (由小写英文字母组成的字符串)。 的名称 N 新生性格鲜明。
的 N 学生将获得学生证 1, 2, 3, \ldots, N in 字典升序 他们的名字。 然而,而不是小写英文字母的普通顺序,其中 a 是最小值并且 z 是最大值,我们使用以下顺序:
- 首先,高桥校长选择一根弦 P 来自 26! 字符串的排列
abcdefghijklmnopqrstuvwxyz长度 26,均匀随机。 - 中较早出现的小写英文字符 P 被认为较小。
对于每个 N 同学,求期望值,取模 998244353,分配的学生 ID(参见注释)。
字典顺序是什么?
一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果以下 1. 和 2. 之一成立。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两个条件:
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}
- S_i 是一个比 T_i.
注释
我们可以证明所求的期望值始终是有理数。 而且,在这个问题的约束下,当值表示为 \frac{P}{Q} 由两个互质整数 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- 第行应包含预期值,模 998244353,分配给学生的学生 ID i.
示例输入 1
3 a aa ab
示例输出 1
1 499122179 499122179
分配给Student的学生ID的期望值 1 is 1;分配给 Student 的学生 ID 的预期值 2 和 3 是 \frac{5}{2}.
请注意,答案应以模数形式打印 998244353。 例如,寻求学生的期望值 2 和 3 is \frac{5}{2}, 我们有 2 \times 499122179 \equiv 5\pmod{998244353}, 所以 499122179 。
示例输入 2
3 a aa aaa
示例输出 2
1 2 3