/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
A_1=0 かつ A_N>0 であるような、N 個の非負整数の組 A=(A_1,A_2,\ldots,A_N) が与えられます。
高橋君は N 個のカウンターを持っており、最初、全てのカウンターの値は 0 です。
高橋君は、全ての 1\leq i\leq N について i 番目のカウンターの値が A_i 以上となるまで次の操作を繰り返します。
N 個のカウンターの中から 1 つを等確率に選び、その値を 0 にする。（選択は毎回独立に行う。）
選んだカウンター 以外 のカウンターの値を 1 増加させる。
高橋君の操作回数の期待値を \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\leq 2\times 10^5
- 0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}
- A_N>0
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
高橋君の操作回数の期待値を \mathrm{mod} 998244353 で出力せよ。
入力例 1
2 0 2
出力例 1
6
i 番目のカウンターの値を C_i で表します。
高橋君の操作が終了するまでの一連の流れの例は次の通りです。
- 1 番目のカウンターの値を 0 にした後、それ以外のカウンターの値を 1 増加させる。 (C_1,C_2)=(0,1) となる。
- 2 番目のカウンターの値を 0 にした後、それ以外のカウンターの値を 1 増加させる。 (C_1,C_2)=(1,0) となる。
- 1 番目のカウンターの値を 0 にした後、それ以外のカウンターの値を 1 増加させる。 (C_1,C_2)=(0,1) となる。
- 1 番目のカウンターの値を 0 にした後、それ以外のカウンターの値を 1 増加させる。 (C_1,C_2)=(0,2) となる。
この場合の操作回数は 4 となります。
1,2,3,4,5,\ldots 回で操作が終了する確率はそれぞれ 0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots であり、 期待値は 2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6 となります。 よって、 6 を出力します。
入力例 2
5 0 1 3 10 1000000000000000000
出力例 2
874839568
Score : 600 points
Problem Statement
You are given a tuple of N non-negative integers A=(A_1,A_2,\ldots,A_N) such that A_1=0 and A_N>0.
Takahashi has N counters. Initially, the values of all counters are 0.
He will repeat the following operation until, for every 1\leq i\leq N, the value of the i-th counter is at least A_i.
Choose one of the N counters uniformly at random and set its value to 0. (Each choice is independent of others.)
Increase the values of the other counters by 1.
Print the expected value of the number of times Takahashi repeats the operation, modulo 998244353 (see Notes).
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} using two coprime integers P and Q, one 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 this R.
Constraints
- 2\leq N\leq 2\times 10^5
- 0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}
- A_N>0
- 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 the expected value of the number of times Takahashi repeats the operation, modulo 998244353.
Sample Input 1
2 0 2
Sample Output 1
6
Let C_i denote the value of the i-th counter.
Here is one possible progression of the process.
- Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,1).
- Set the value of the 2-nd counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(1,0).
- Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,1).
- Set the value of the 1-st counter to 0, and then increase the value of the other counter by 1. Now, (C_1,C_2)=(0,2).
In this case, the operation is performed four times.
The probabilities that the process ends after exactly 1,2,3,4,5,\ldots operation(s) are 0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots, respectively, so the sought expected value is 2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6. Thus, 6 should be printed.
Sample Input 2
5 0 1 3 10 1000000000000000000
Sample Output 2
874839568