AT_abc231_g [ABC231G] Balls in Boxes

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的箱子。最初，第 $i$ 个箱子中有 $A_i$ 个球。

你需要重复进行 $K$ 次如下操作：

• 从 $N$ 个箱子中等概率地随机选择一个（每次操作的选择相互独立）。在选中的箱子中加入 $1$ 个球。

$K$ 次操作结束后，设第 $i$ 个箱子中的球数为 $B_i$，则得分为所有箱子球数的乘积 $\prod_{i=1}^{N} B_i$。

请你计算得分的期望值，并对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 1
1 2 3

输出 #1

665496245

输入输出样例 #2

输入 #2

2 2
1 2

输出 #2

499122182

输入输出样例 #3

输入 #3

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

输出 #3

138512322

说明/提示

注意

若所求期望值可表示为最简分数 $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$

样例解释 1

操作后，得分如下：

• 操作选择箱子 $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

操作后，得分如下：

• 第 $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}$。

由 ChatGPT 4.1 翻译