分数: 600 点
问题陈述
我们有 N 盒子编号 1 to N。最初,盒子 i 包含 A_i 球。
您将重复以下操作 K 次。
- 从以下选项中选择一个框 N 均匀随机(每次独立)。将一个球添加到所选框中。
让 B_i 是 Box 中的球数 i 之后 K 操作,以及 分数 是球数量的乘积, \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
运行后,得分如下。
- 选择 Box 时 1 在操作中, 2\times 2\times 3=12.
- 选择 Box 时 2 在操作中, 1\times 3\times 3=9.
- 选择 Box 时 3 在操作中, 1\times 2\times 4=8.
因此,所讨论的期望值是 \frac{1}{3}(12+9+8)=\frac{29}{3}。该值取模 998244353 is 665496245.
示例输入 2
2 2 1 2
示例输出 2
499122182
运算后,得分如下。
- 选择 Box 时 1 在第一个操作和框中 1 在第二个, 3\times 2=6.
- 选择 Box 时 1 在第一个操作和框中 2 在第二个, 2\times 3=6.
- 选择 Box 时 2 在第一个操作和框中 1 在第二个, 2\times 3=6.
- 选择 Box 时 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