103526: [Atcoder]ABC352 G - Socks 3
Description
Score: $600$ points
Problem Statement
Takahashi has various colors of socks in his chest of drawers. The colors of the socks are represented by integers from $1$ to $N$, and there are $A_i\ (\geq 2)$ socks of color $i$.
He is about to choose which socks to wear today by performing the following operation:
- Continue to randomly draw one sock at a time from the chest, with equal probability, until he can make a pair of socks of the same color from those he has already drawn. Once a sock is drawn, it will not be returned to the chest.
Find the expected value, modulo $998244353$, of the number of times he has to draw a sock from the chest.
What does it mean to find the expected value modulo $998244353$?
It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if the expected value is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$. Here, there exists a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Find this $z$.Constraints
- $1\leq N \leq 3\times 10^5$
- $2\leq A_i \leq 3000$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer.
Sample Input 1
2 2 2
Sample Output 1
665496238
For example, the operation could be performed as follows:
- Draw a sock of color $1$ from the chest. There remains one sock of color $1$ and two socks of color $2$ in the chest.
- Draw a sock of color $2$ from the chest. There remains one sock each of colors $1$ and $2$ in the chest.
- Draw a sock of color $1$ from the chest. The socks drawn so far are two of color $1$ and one of color $2$, allowing a pair of color $1$ socks to be made, thus ending the operation.
In this example, Takahashi draws a sock from the chest three times.
The expected number of times Takahashi draws a sock from the chest is $3$ with probability $\frac{2}{3}$ and $2$ with probability $\frac{1}{3}$, so the expected value is $3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}$.
Sample Input 2
1 352
Sample Output 2
2
Sample Input 3
6 1796 905 2768 253 2713 1448
Sample Output 3
887165507
Input
Output
问题描述
高桥的抽屉里有各种颜色的袜子。袜子的颜色用从1到N的整数表示，每种颜色有$A_i\ (\geq 2)$只袜子。
他打算通过以下操作来选择今天要穿的袜子：
- 以相等的概率继续从抽屉中随机抽出一只袜子，直到他能从已经抽出的袜子中组成一对同色的袜子。一旦抽出一只袜子，它就不会再放回抽屉。
找出他必须从抽屉中抽出袜子的次数的期望值，对998244353取模。
什么是找到对998244353取模的期望值？
可以证明，所求的期望值总是有理数。此外，本问题的约束条件保证，如果期望值表示为不可约分数$\frac{y}{x}$，则$x$不会被998244353整除。存在一个唯一的整数$z$，范围在0到998244352（含）之间，满足$xz \equiv y \pmod{998244353}$。找出这个$z$。约束条件
- $1\leq N \leq 3\times 10^5$
- $2\leq A_i \leq 3000$
- 所有输入值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $A_1$ $A_2$ $\dots$ $A_N$
输出
打印答案。
样例输入1
2 2 2
样例输出1
665496238
例如，操作可以如下进行：
- 从抽屉中抽出一只颜色为1的袜子。抽屉里剩下一只颜色为1的袜子和两只颜色为2的袜子。
- 从抽屉中抽出一只颜色为2的袜子。抽屉里剩下一只颜色为1的袜子和一只颜色为2的袜子。
- 从抽屉中抽出一只颜色为1的袜子。迄今为止抽出的袜子是两只颜色为1的和一只颜色为2的，可以组成一对颜色为1的袜子，操作结束。
在这个例子中，高桥从抽屉里抽出袜子三次。
高桥抽袜子的次数的期望数是3次的概率为$\frac{2}{3}$，2次的概率为$\frac{1}{3}$，所以期望值是$3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}$。
样例输入2
1 352
样例输出2
2
样例输入3
6 1796 905 2768 253 2713 1448
样例输出3
887165507