收集全部

题目描述

一个盒子里有 $N$ 张卡片。每张卡片上写着一个整数,它在 $1$ 到 $M$ 之间(含端点)。对每个 $i=1,\ldots,M$,写着数字 $i$ 的卡片有 $C_i$ 张。

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

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

求直到笔记本中 $1$ 到 $M$ 的所有整数都至少写了一次为止,所需操作次数的期望值(对 $998244353$ 取模)。

期望值对 $998244353$ 取模的方法

可以证明,本题所求的期望值始终是有理数。并且,本题的数据范围保证:当期望值表示为既约分数 $\frac yx$ 时,分母 $x$ 不被 $998244353$ 整除。

此时,存在唯一的 $0\leq z\lt998244353$ 满足 $y\equiv xz\pmod{998244353}$。请输出这个 $z$。

输入格式

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

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

输出格式

输出答案。

样例

2 2
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$。

5 2
4 1

748683270

期望值为 $\frac{21}{4}$,它对 $998244353$ 取模的表示是 $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

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

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

918012973

数据范围

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