← 返回题目列表

AtCoder · abc268_g

G. 随机学生证

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

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

  1. |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 存在一个整数 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