/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 575 点
問題文
長さ N の非負整数列 A が与えられます。
A の要素数が 1 になるまで、以下の操作を繰り返し行います。
- 1 \leq i,j \leq |A| を満たす相異なる 2 整数 i,j を一様ランダムに選ぶ。
- A_i,A_j をそれぞれ a,b と置く。
- A から i 番目の要素と j 番目の要素を削除する。
- A の末尾に a-b を追加する。
最終的な A の唯一の要素を x とします。 x^2 の期待値を \mod 998244353 で求めてください。
期待値 \pmod{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 998244352
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを 1 行で出力せよ。
入力例 1
3 4 5 0
出力例 1
665496263
まず (i,j) として (3,1) を選ぶと、数列は (5,-4) になります。
次に (i,j) として (1,2) を選ぶと、数列は (9) になります。
x^2 は \frac{1}{3} の確率で 81、 \frac{2}{3} の確率で 1 になり、期待値は \frac{83}{3} です。
入力例 2
5 450 2026 3 21 100
出力例 2
669406799
Score : 575 points
Problem Statement
You are given a sequence A of N non-negative integers.
Repeat the following operation until A has exactly one element.
- Choose two distinct integers i and j satisfying 1 \leq i, j \leq |A| uniformly at random.
- Let a and b be A_i and A_j, respectively.
- Remove the i-th and j-th elements from A.
- Append a - b to the end of A.
Let x be the only element of A at the end. Find the expected value of x^2, modulo 998244353.
Definition of expected value modulo 998244353
It can be proved that the expected value to be found is always a rational number. It can also be proved that under the constraints of this problem, when expressed as an irreducible fraction \frac{P}{Q}, we have Q \neq 0 \pmod{998244353}. Thus, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 998244352
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Output the answer on a single line.
Sample Input 1
3 4 5 0
Sample Output 1
665496263
First, choosing (i, j) = (3, 1) makes the sequence (5, -4).
Next, choosing (i, j) = (1, 2) makes the sequence (9).
x^2 equals 81 with probability \frac{1}{3} and 1 with probability \frac{2}{3}, so the expected value is \frac{83}{3}.
Sample Input 2
5 450 2026 3 21 100
Sample Output 2
669406799