/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
カード 1, カード 2, \ldots, カード N の N 枚のカードがあり、 カード i (1\leq i\leq N) には整数 A_i が書かれています。
K=1,2,\ldots,N について、次の問題を解いてください。
カード 1, カード 2, \ldots, カード K の K 枚のカードが入っている袋があります。
次の操作を 2 回繰り返し、記録された数を順に x,y とします。袋から無作為にカードを 1 枚取り出し、カードに書かれている数を記録する。その後、カードを 袋の中に戻す 。
\max(x,y) の値の期待値を \text{mod} 998244353 で出力してください（注記参照）。
ただし、\max(x,y) で x と y のうち小さくない方の値を表します。
注記
求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を出力してください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 行出力せよ。 i 行目 (1\leq i\leq N) には、K=i の時の問題に対する答えを出力せよ。
入力例 1
3 5 7 5
出力例 1
5 499122183 443664163
例えば、K=2 の時の答えは次のようにして求まります。
袋の中にはカード 1 とカード 2 が入っており、それぞれには A_1=5 と A_2=7 が書かれています。
- 1 回目に取り出されたカードがカード 1 、2 回目に取り出されたカードもカード 1 のとき、x=y=5 であり、\max(x,y)=5 となります。
- 1 回目に取り出されたカードがカード 1 、2 回目に取り出されたカードはカード 2 のとき、x=5, y=7 であり、\max(x,y)=7 となります。
- 1 回目に取り出されたカードがカード 2 、2 回目に取り出されたカードはカード 1 のとき、x=7, y=5 であり、\max(x,y)=7 となります。
- 1 回目に取り出されたカードがカード 2 、2 回目に取り出されたカードもカード 2 のとき、x=y=7 であり、\max(x,y)=7 となります。
これらが等確率で起こるため、期待値は \frac{5+7+7+7}{4}=\frac{13}{2} となります。 499122183\times 2\equiv 13 \pmod{998244353} であるため、499122183 を出力します。
入力例 2
7 22 75 26 45 72 81 47
出力例 2
22 249561150 110916092 873463862 279508479 360477194 529680742
Score : 500 points
Problem Statement
There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.
For K=1, 2, \ldots, N, solve the following problem.
We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.
Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).
Notes
It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 2\times 10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print N lines. The i-th line (1\leq i\leq N) should contain the answer to the problem for K=i.
Sample Input 1
3 5 7 5
Sample Output 1
5 499122183 443664163
For instance, the answer for K=2 is found as follows.
The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.
- If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
- If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
- If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
- If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.
These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.
Sample Input 2
7 22 75 26 45 72 81 47
Sample Output 2
22 249561150 110916092 873463862 279508479 360477194 529680742