102686: [AtCoder]ABC268 G - Random Student ID

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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 abcdefghijklmnopqrstuvwxyz of 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.

  1. $|S| \lt |T|$ and $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$.
  2. 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$的长度。

  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$行应该包含分配给学生$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

加入题单

上一题 下一题 算法标签: