AT_abc268_g [ABC268G] Random Student ID

[problemUrl]: https://atcoder.jp/contests/abc268/tasks/abc268_g 高橋小学校には $ 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 $ の長さを表します。 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 $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ S_1S_2\ldots\ S_{i-1}\ =\ T_1T_2\ldots\ T_{i-1} $ - $ S_i $ が $ T_i $ より小さい文字である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

$ N $行出力せよ。 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ i $ 行目には $ i $ 番目の新入生に与えられる学籍番号の期待値を $ \mathrm{mod}\,\ 998244353 $ で出力せよ。

### 注記 求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 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 $ ### Sample Explanation 1 $ 1 $ 番目の新入生に与えられる学籍番号の期待値は $ 1 $ であり、$ 2,\ 3 $ 番目の新入生に与えられる学籍番号の期待値は $ \frac{5}{2} $ です。 答えを $ \mathrm{mod}\,\ 998244353 $ で出力することに注意してください。 例えば、$ 2,\ 3 $ 番目の新入生についての出力では、求める期待値が $ \frac{5}{2} $ であり、 $ 2\ \times\ 499122179\ \equiv\ 5\pmod{998244353} $ が成り立つので、 $ 499122179 $ を出力します。