AT_abc331_g [ABC331G] Collect Them All

题目描述

箱子里有 $N$ 张卡片。每张卡片上写有一个 $1$ 到 $M$ 之间的整数，对于每个 $i=1,\ldots,M$，写有 $i$ 的卡片有 $C_i$ 张。

你手上有一本空白的笔记本，你会重复以下操作：

• 从箱子中随机取出一张卡片。把卡片上写的整数记在笔记本上，然后把卡片放回箱子。

请你求出，直到笔记本上 $1$ 到 $M$ 的每个整数都至少被记过一次为止，所需操作次数的期望值，并对 $998244353$ 取模。

期望值 ${}\bmod{998244353}$ 的定义
本题中要求的期望值一定是有理数。在本题的约束下，设期望值为最简分数 $\frac{y}{x}$，保证 $x$ 不能被 $998244353$ 整除。此时，存在唯一的 $0\leq z<998244353$ 满足 $y\equiv xz\pmod{998244353}$，请输出 $z$。

输入格式

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

$N$ $M$ $C_1$ $\ldots$ $C_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 2
1 1

输出 #1

3

输入输出样例 #2

输入 #2

5 2
4 1

输出 #2

748683270

输入输出样例 #3

输入 #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

输入输出样例 #4

输入 #4

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

输出 #4

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$，笔记本上有 $1$ 两次。
• 第三次取出的卡片上写着 $2$，笔记本上有 $1$ 两次，$2$ 一次。
  所求的期望值为 $2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3$。

样例解释 2

所求的期望值为 $\frac{21}{4}$，对 $998244353$ 取模后为 $748683270$。

样例解释 3

所求的期望值为 $\frac{13943237577224054960759}{61980890084919934128}$。

由 ChatGPT 4.1 翻译