← 返回题目列表

AtCoder · abc231_g

G. 盒子里的球

中文机器翻译题面 查看原题

分数: 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