← 返回题目列表

AtCoder · abc331_g

G. 收集全部

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

分数: 625 点

问题陈述

有 N 盒子里的卡片。每张卡片上都写有一个整数,介于 1 和 M,包括在内。对于每个 i=1,\ldots,M,有 C_i 卡片编号 上面写着 i 。

从空笔记本开始,重复以下操作:

  • 从盒子里随机抽一张牌。将卡上的整数写在笔记本中,然后将卡放回盒子中。

求期望值,模 998244353,执行操作的次数,直到笔记本拥有来自 1 to M 至少写过一次。

如何求期望值模 998244353 可以证明此问题中寻求的期望值始终是有理数。此外,该问题的约束保证当期望值表示为不可约分数时 \frac yx,分母 x 不能被整除 998244353。 那么,还有一个独特的 0\leq z\lt998244353 这样 y\equiv xz\pmod{998244353}。打印此内容 z.

约束

  • 1 \leq M \leq N \leq 2\times 10^5
  • 1 \leq C_i
  • \sum_{i=1}^{M}C_i=N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
C_1 \ldots C_M

输出

打印答案。


示例输入 1

2 2
1 1

示例输出 1

3

这一系列操作可以如下进行:

  • 你抽一张牌 上面写着 1 。笔记本现在有一个 里面写着 1 。
  • 你再次抓一张牌 上面写着 1 。笔记本现在有两个 里面写着 1。
  • 你抽一张牌 上面写着 2 。笔记本现在有两个 里面写着 1和一 2 。

寻求的期望值为 2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3.


示例输入 2

5 2
4 1

示例输出 2

748683270

预期值为 \frac{21}{4},其表示模 998244353 is 748683270.


示例输入 3

50 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

示例输出 3

244742906

预期值为 \frac{13943237577224054960759}{61980890084919934128}.


示例输入 4

74070 15
1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333

示例输出 4

918012973