Random Student ID

题目描述

Takahashi 小学有 $N$ 名新学生。对于 $i = 1, 2, \ldots, N$，第 $i$ 名新学生的名字是 $S_i$（由小写英文字母组成的字符串）。 这 $N$ 个新学生的名字两两不同。 这 $N$ 名学生将按照名字的字典序升序被分配学号 $1, 2, 3, \ldots, N$。然而，我们使用的字母顺序不是普通的将 $a$ 视为最小、$z$ 视为最大的顺序，而是如下顺序：

首先，Takahashi 校长从长度为 $26$ 的字符串 $abcdefghijklmnopqrstuvwxyz$ 的 $26!$ 种排列中，均匀随机地选择一个字符串 $P$。 在 $P$ 中出现得更靠前的小写英文字母被认为更小。

对于每一名 $N$ 名学生，求被分配到的学号的期望值，对 $998244353$ 取模（参见说明）。

输入格式

输入来自标准输入，格式如下： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

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

3
a
aa
ab

1
499122179
499122179

3
a
aa
aaa

1
2
3

提示

$2 \leq N$ $N$ 是整数。 $S_i$ 是长度至少为 $1$ 的由小写英文字母组成的字符串。 给定字符串长度之和至多为 $5 \times 10^5$。 $i \neq j \Rightarrow S_i \neq S_j$我们可以证明所求的期望值总是有理数。此外，在本题的约束下，当该值表示为互质整数 $P$ 和 $Q$ 的 $\frac{P}{Q}$ 时，我们可以证明存在唯一整数 $R$ 使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求出这样的 $R$。学生 1 被分配学号的期望值是 $1$；学生 2 和 3 被分配学号的期望值是 $\frac{5}{2}$。 注意答案应当对 $998244353$ 取模。 例如，学生 2 和 3 的所求期望值为 $\frac{5}{2}$， 且 $2 \times 499122179 \equiv 5\pmod{998244353}$， 因此应当输出 $499122179$。

标签: AtCoder|abc268G

来源

AtCoder|abc268G