Collect Them All

题目描述

盒子里有 $N$ 张卡片。每张卡片上写着一个介于 $1$ 到 $M$（含）之间的整数。对于每个 $i=1,\ldots,M$，有 $C_i$ 张写有数字 $i$ 的卡片。 从一本空笔记本开始，重复以下操作：

随机从盒子里抽一张卡片。把卡片上的整数写到笔记本里，然后把卡片放回盒子。

求直到笔记本上至少各写到一次 $1$ 到 $M$ 的整数为止，所进行操作次数的期望值，对 $998244353$ 取模的结果。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $C_1$ $\ldots$ $C_M$

输出格式

输出答案。

2 2
1 1

3

5 2
4 1

748683270

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

244742906

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

918012973

提示

$1 \leq M \leq N \leq 2\times 10^5$ $1 \leq C_i$ $\sum_{i=1}^{M}C_i=N$ 所有输入值均为整数。操作序列可能如下进行：

你抽到了一张写有 $1$ 的卡片。笔记本现在写着一个 $1$。 你又抽到了一张写有 $1$ 的卡片。笔记本现在写着两个 $1$。 你抽到了一张写有 $2$ 的卡片。笔记本现在写着两个 $1$ 和一个 $2$。

所求的期望值为 $2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3$.
期望值为 $\frac{21}{4}$，其在 $998244353$ 意义下的表示为 $748683270$.
期望值为 $\frac{13943237577224054960759}{61980890084919934128}$.

标签: AtCoder|abc331G

来源

AtCoder|abc331G