Balls in Boxes

题目描述

我们有编号为 $1$ 到 $N$ 的 $N$ 个盒子。最初，第 $i$ 个盒子包含 $A_i$ 个球。 你将重复以下操作 $K$ 次。

每次从 $N$ 个盒子中等概率随机选择一个盒子（每次独立）。向被选中的盒子中加入一个球。

令 $B_i$ 为在 $K$ 次操作后第 $i$ 个盒子中的球数，得分 为各盒子中球数的乘积，$\prod_{i=1}^{N}B_i$。 求得分的期望值模 $998244353$。

输入格式

输入由标准输入按照以下格式给出： $N$ $K$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

3 1
1 2 3

665496245

2 2
1 2

499122182

10 1000000000
998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359

138512322

提示

$1 \leq N \leq 1000$ $1 \leq K \leq 10^9$ $0 \leq A_i \leq 10^9$当所求的期望值表示为最简分数 $p/q$ 时，存在唯一的整数 $r$，使得 $rq\equiv p \pmod{998244353}$ 且 $0\leq r < 998244353$，在本题的约束下该 $r$ 即为我们要求的值。操作之后，得分如下。

当在操作中选择盒子 $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$.
在操作之后，得分如下。

当第一次操作选择盒子 $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}$.

标签: AtCoder|abc231G

来源

AtCoder|abc231G