/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋小学校には N 人の新入生がおり、i = 1, 2, \ldots, N について i 番目の新入生の名前は S_i （英小文字のみからなる文字列）です。 N 人の名前は相異なります。
N 人の新入生には、名前が辞書順で小さい者から順に 1, 2, 3, \ldots, N と学籍番号が付与されます。
ただしその際には、a が最小で z が最大である通常の英小文字の順序の代わりに、下記で定まる順序を用います。
- まず高橋校長が、長さ 26 の文字列
abcdefghijklmnopqrstuvwxyzを並べ替えて得られる 26! 個の文字列の中から 1 つを、等確率でランダムに文字列 P として選ぶ。 - P で前にある英小文字ほど小さい英小文字とみなす。
N 人の新入生それぞれについて、与えられる学籍番号の期待値を \mathrm{mod}\, 998244353 で出力してください（注記参照）。
辞書順で小さいとは？
文字列 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 が存在して、下記の 2 つがともに成り立つ。
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}
- S_i が T_i より小さい文字である。
注記
求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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 番目の新入生に与えられる学籍番号の期待値を \mathrm{mod}\, 998244353 で出力せよ。
入力例 1
3 a aa ab
出力例 1
1 499122179 499122179
1 番目の新入生に与えられる学籍番号の期待値は 1 であり、2, 3 番目の新入生に与えられる学籍番号の期待値は \frac{5}{2} です。
答えを \mathrm{mod}\, 998244353 で出力することに注意してください。 例えば、2, 3 番目の新入生についての出力では、求める期待値が \frac{5}{2} であり、 2 \times 499122179 \equiv 5\pmod{998244353} が成り立つので、 499122179 を出力します。
入力例 2
3 a aa aaa
出力例 2
1 2 3
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