102316: [AtCoder]ABC231 G - Balls in Boxes

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

有 $n$ 个盒子,初始时第 $i$ 个盒子内有 $a_i$ 个小球,进行 $k$ 次操作后,每次操作等概率随机选择一个盒子放入一个小球,设 $k$ 次操作后每个盒子的小球个数为 $b_i$,那么得分为 $\prod_{i=1}^n b_i$。求出期望得分。 - $n\leq 1000,k,a_i\leq 10^9$

Output

得分:$600$分

问题描述

我们有编号为$1$到$N$的$N$个盒子。最初,第$i$个盒子包含$A_i$个球。

你将重复以下$K$次操作:

  • 从$N$个盒子中随机选择一个(每次独立)。向所选盒子中添加一个球。

设$B_i$是在$K$次操作后第$i$个盒子中的球数,得分定义为球数的乘积$\prod_{i=1}^{N}B_i$。

求得分的期望值对$998244353$取模的结果。

注意

当问题中的期望值表示为不可约分数$p/q$时,根据本问题的约束条件,存在一个唯一的整数$r$,使得$rq\equiv p \pmod{998244353}$且$0\leq r < 998244353$。我们所寻找的就是这个$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}$。这个值对$998244353$取模的结果为$665496245$。


样例输入2

2 2
1 2

样例输出2

499122182

操作后,得分如下:

  • 当在第一次操作中选择第1个盒子,在第二次操作中选择第1个盒子时,$3\times 2=6$。
  • 当在第一次操作中选择第1个盒子,在第二次操作中选择第2个盒子时,$2\times 3=6$。
  • 当在第一次操作中选择第2个盒子,在第二次操作中选择第1个盒子时,$2\times 3=6$。
  • 当在第一次操作中选择第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

加入题单

上一题 下一题 算法标签: