Socks 3

题目描述

Takahashi 在他的抽屉里有各种颜色的袜子。 袜子的颜色用整数 $1$ 到 $N$ 表示，并且颜色为 $i$ 的袜子共有 $A_i\ (\geq 2)$ 只。 他将通过执行以下操作来决定今天要穿哪双袜子：

继续以相等的概率一次随机从抽屉中抽取一只袜子，直到他可以从已经抽到的袜子中配成一双同颜色的袜子为止。 一旦一只袜子被抽出，就不会被放回抽屉。

求抽取袜子次数的期望值对 $998244353$ 取模后的结果。

“对 $998244353$ 取模的期望值”是什么意思？

可以证明，所求的期望值总是有理数。 此外，本题的约束保证若将期望值表示为既约分数 $\frac{y}{x}$，则 $x$ 不被 $998244353$ 整除。 因此存在一个唯一的整数 $z$，满足 $0\le z\le 998244352$ 且 $xz \equiv y \pmod{998244353}$。求这个 $z$。

输入格式

输入按照下述格式由标准输入给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

2
2 2

665496238

1
352

2

6
1796 905 2768 253 2713 1448

887165507

提示

$1\leq N \leq 3\times 10^5$ $2\leq A_i \leq 3000$ 所有输入值均为整数。例如，操作可能按如下方式进行：

从抽屉中抽出一只颜色为 $1$ 的袜子。抽屉中剩下颜色 $1$ 的一只袜子和颜色 $2$ 的两只袜子。 从抽屉中抽出一只颜色为 $2$ 的袜子。抽屉中剩下颜色 $1$ 和 $2$ 各一只袜子。 从抽屉中抽出一只颜色为 $1$ 的袜子。到目前为止抽到的袜子中有两只颜色为 $1$ 的袜子和一只颜色为 $2$ 的袜子，因此可以配成一双颜色为 $1$ 的袜子，操作结束。

在这个例子中，Takahashi 抽取了三次袜子。 抽取次数为 $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}$。

标签: AtCoder|abc352G

来源

AtCoder|abc352G