102686: [AtCoder]ABC268 G - Random Student ID
Description
Score : $600$ points
Problem Statement
Takahashi Elementary School has $N$ new students. For $i = 1, 2, \ldots, N$, the name of the $i$-th new student is $S_i$ (which is a string consisting of lowercase English letters). The names of the $N$ new students are distinct.
The $N$ students will be assigned a student ID $1, 2, 3, \ldots, N$ in ascending lexicographical order of their names. However, instead of the ordinary order of lowercase English letters where a is the minimum and z is the maximum, we use the following order:
- First, Principal Takahashi chooses a string $P$ from the $26!$ permutations of the string
abcdefghijklmnopqrstuvwxyzof length $26$, uniformly at random. - The lowercase English characters that occur earlier in $P$ are considered smaller.
For each of the $N$ students, find the expected value, modulo $998244353$, of the student ID assigned (see Notes).
What is the lexicographical order?
A string $S = S_1S_2\ldots S_{|S|}$ is said to be lexicographically smaller than a string $T = T_1T_2\ldots T_{|T|}$ if one of the following 1. and 2. holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.
- $|S| \lt |T|$ and $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$.
- There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ satisfying the following two conditions:
- $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$
- $S_i$ is a smaller character than $T_i$.
Notes
We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as $\frac{P}{Q}$ by two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find such $R$.
Constraints
- $2 \leq N$
- $N$ is an integer.
- $S_i$ is a string of length at least $1$ consisting of lowercase English letters.
- The sum of lengths of the given strings is at most $5 \times 10^5$.
- $i \neq j \Rightarrow S_i \neq S_j$
Input
Input is given from Standard Input in the following format:
$N$ $S_1$ $S_2$ $\vdots$ $S_N$
Output
Print $N$ lines. For each $i = 1, 2, \ldots, N$, the $i$-th line should contain the expected value, modulo $998244353$, of the student ID assigned to Student $i$.
Sample Input 1
3 a aa ab
Sample Output 1
1 499122179 499122179
The expected value of the student ID assigned to Student $1$ is $1$; the expected values of the student ID assigned to Student $2$ and $3$ are $\frac{5}{2}$.
Note that the answer should be printed modulo $998244353$. For example, the sought expected value for Student $2$ and $3$ is $\frac{5}{2}$, and we have $2 \times 499122179 \equiv 5\pmod{998244353}$, so $499122179$ should be printed.
Sample Input 2
3 a aa aaa
Sample Output 2
1 2 3
Input
题意翻译
**题目大意** 有 $n$ 个学生，第 $i$ 个学生的名字是一个字符串 $S_i$，编号是 $i$。 接下来校长要按照一种绝妙的字典序来对这 $n$ 个学生的名字排序。他随机选取一个 $\tt{a}\sim\tt{z}$ 的排列，定为 $P$。$P$ 中越早出现的字母，他的字典序就越小。 对于每一个学生，求出他的期望排名，对 $998244353$ 取模。 **输入格式** 第一行一个整数 $n$。 接下来 $n$ 行每行一个字符串 $S_i$。 **输出格式** 输出 $n$ 行，第 $i$ 行表示编号为 $i$ 的学生的期望排名。 **数据范围** 对于所有数据，我们保证 $S_i$ 只由小写字母组成，并且这些学生的名字互不相同。$n\geqslant 2$，字符串总长度不超过 $5\times 10^5$。Output
分数：$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的期望值（见注释）。
什么是字典序升序？
一个字符串$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$行应该包含分配给学生$i$的学生ID的期望值（模$998244353$）。
样例输入1
3 a aa ab
样例输出1
1 499122179 499122179
分配给学生1的学生ID的期望值为$1$；分配给学生2和3的学生ID的期望值为$\frac{5}{2}$。
注意答案应模$998244353$打印。 例如，对于学生2和3所求的期望值为$\frac{5}{2}$， 我们有$2 \times 499122179 \equiv 5\pmod{998244353}$， 所以应该打印$499122179$。
样例输入2
3 a aa aaa
样例输出2
1 2 3