103316: [Atcoder]ABC331 G - Collect Them All
Description
Score : $625$ points
Problem Statement
There are $N$ cards in a box. Each card has an integer written on it, which is between $1$ and $M$, inclusive. For each $i=1,\ldots,M$, there are $C_i$ cards with the number $i$ written on them.
Starting with an empty notebook, you repeat the following operation:
- Randomly draw one card from the box. Write the integer on the card in the notebook, then return the card to the box.
Find the expected value, modulo $998244353$, of the number of times the operation is performed until the notebook has all integers from $1$ to $M$ written at least once.
How to find an expected value modulo $998244353$
The expected value sought in this problem can be proven to always be a rational number. Furthermore, the constraints of this problem guarantee that when the expected value is expressed as an irreducible fraction $\frac yx$, the denominator $x$ is not divisible by $998244353$. Then, there is a unique $0\leq z\lt998244353$ such that $y\equiv xz\pmod{998244353}$. Print this $z$.Constraints
- $1 \leq M \leq N \leq 2\times 10^5$
- $1 \leq C_i$
- $\sum_{i=1}^{M}C_i=N$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $C_1$ $\ldots$ $C_M$
Output
Print the answer.
Sample Input 1
2 2 1 1
Sample Output 1
3
The series of operations may proceed as follows:
- You draw a card with $1$ written on it. The notebook now has one $1$ written in it.
- You again draw a card with $1$ written on it. The notebook now has two $1$s written in it.
- You draw a card with $2$ written on it. The notebook now has two $1$s and one $2$ written in it.
The sought expected value is $2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3$.
Sample Input 2
5 2 4 1
Sample Output 2
748683270
The expected value is $\frac{21}{4}$, whose representation modulo $998244353$ is $748683270$.
Sample Input 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
Sample Output 3
244742906
The expected value is $\frac{13943237577224054960759}{61980890084919934128}$.
Sample Input 4
74070 15 1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333
Sample Output 4
918012973
Input
Output
分数：$625$分
问题描述
盒子里有$N$张卡片。每张卡片上都写有一个整数，范围在$1$到$M$之间，包括$1$和$M$。对于每个$i=1,\ldots,M$，有$C_i$张写有数字$i$的卡片。
从一个空的笔记本开始，你重复以下操作：
- 从盒子里随机抽取一张卡片。在笔记本上写下卡片上的整数，然后将卡片放回盒子。
求出直到笔记本上至少写有$1$到$M$之间的所有整数为止，需要进行这个操作的期望次数（对$998244353$取模）。
如何求对$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$取模的结果为$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