/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N の番号がついた N 個の箱があります。最初、箱 i には A_i 個のボールが入っています。
あなたは次の操作を K 回繰り返します。
- N 個の箱の中から等確率で 1 個選ぶ(この選択は操作ごとに独立である)。選んだ箱にボールを 1 個追加する。
K 回の操作が終了した後で箱 i に入っているボールの個数を B_i とするとき、スコアはボールの個数の総積 \prod_{i=1}^{N}B_i になります。
スコアの期待値を \bmod 998244353 で求めてください。
注意
求める期待値が既約分数 p/q で表されるとき、rq\equiv p \pmod{998244353} かつ 0\leq r < 998244353 を満たす整数 r がこの問題の制約のもとで一意に定まります。この r が求める値です。
制約
- 1 \leq N \leq 1000
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 1 1 2 3
出力例 1
665496245
操作の結果、スコアは次のようになります。
- 操作で箱 1 を選んだとき、2\times 2\times 3=12
- 操作で箱 2 を選んだとき、1\times 3\times 3=9
- 操作で箱 3 を選んだとき、1\times 2\times 4=8
したがって、求める期待値は \frac{1}{3}(12+9+8)=\frac{29}{3} となります。これを \bmod 998244353 で表すと 665496245 になります。
入力例 2
2 2 1 2
出力例 2
499122182
操作の結果、スコアは次のようになります。
- 1 回目の操作で箱 1 を選び、2 回目の操作で箱 1 を選んだとき、3\times 2=6
- 1 回目の操作で箱 1 を選び、2 回目の操作で箱 2 を選んだとき、2\times 3=6
- 1 回目の操作で箱 2 を選び、2 回目の操作で箱 1 を選んだとき、2\times 3=6
- 1 回目の操作で箱 2 を選び、2 回目の操作で箱 2 を選んだとき、1\times 4=4
したがって、求める期待値は \frac{1}{4}(6+6+6+4)=\frac{11}{2} となります。
入力例 3
10 1000000000 998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359
出力例 3
138512322
Score : 600 points
Problem Statement
We have N boxes numbered 1 to N. Initially, Box i contains A_i balls.
You will repeat the following operation K times.
- Choose one box out of the N uniformly at random (each time independently). Add one ball to the chosen box.
Let B_i be the number of balls in Box i after the K operations, and the score be the product of the numbers of balls, \prod_{i=1}^{N}B_i.
Find the expected value of the score modulo 998244353.
Notes
When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq\equiv p \pmod{998244353} and 0\leq r < 998244353 under the Constraints of this problem. This r is the value we seek.
Constraints
- 1 \leq N \leq 1000
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N K A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
3 1 1 2 3
Sample Output 1
665496245
After the operation, the score will be as follows.
- When choosing Box 1 in the operation, 2\times 2\times 3=12.
- When choosing Box 2 in the operation, 1\times 3\times 3=9.
- When choosing Box 3 in the operation, 1\times 2\times 4=8.
Therefore, the expected value in question is \frac{1}{3}(12+9+8)=\frac{29}{3}. This value modulo 998244353 is 665496245.
Sample Input 2
2 2 1 2
Sample Output 2
499122182
After the operations, the score will be as follows.
- When choosing Box 1 in the first operation and Box 1 in the second, 3\times 2=6.
- When choosing Box 1 in the first operation and Box 2 in the second, 2\times 3=6.
- When choosing Box 2 in the first operation and Box 1 in the second, 2\times 3=6.
- When choosing Box 2 in the first operation and Box 2 in the second, 1\times 4=4.
Therefore, the expected value in question is \frac{1}{4}(6+6+6+4)=\frac{11}{2}.
Sample Input 3
10 1000000000 998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359
Sample Output 3
138512322