AT_abc352_g [ABC352G] Socks 3

题目描述

高桥君的抽屉里有各种颜色的袜子。袜子的颜色用 $1$ 到 $N$ 之间的整数表示，颜色 $i$ 的袜子有 $A_i\ (\geq\ 2)$ 双。

高桥君打算通过以下操作选择今天要穿的袜子：

• 不断从抽屉中随机且等概率地取出一只袜子，直到在已经取出的袜子中，某种颜色的袜子可以组成一对为止。取出的袜子不会放回抽屉。

请你求出高桥君从抽屉中取袜子的次数的期望值，并对 $998244353$ 取模。

所谓对 $998244353$ 取模的期望值，是指期望值一定可以表示为一个最简分数 $\frac{y}{x}$，并且在本题的约束下，$x$ 保证不会被 $998244353$ 整除。此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$ 满足 $xz \equiv y \pmod{998244353}$，请输出这个 $z$。

输入格式

输入为以下格式，从标准输入读入。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
2 2

输出 #1

665496238

输入输出样例 #2

输入 #2

1
352

输出 #2

2

输入输出样例 #3

输入 #3

6
1796 905 2768 253 2713 1448

输出 #3

887165507

说明/提示

约束条件

• $1 \leq N \leq 3 \times 10^5$
• $2 \leq A_i \leq 3000$
• 输入均为整数

样例解释 1

例如，可以按如下方式进行操作：

1. 从抽屉中取出一只颜色为 $1$ 的袜子。此时抽屉中还剩 $1$ 只颜色为 $1$ 的袜子和 $2$ 只颜色为 $2$ 的袜子。
2. 从抽屉中取出一只颜色为 $2$ 的袜子。此时抽屉中还剩 $1$ 只颜色为 $1$ 的袜子和 $1$ 只颜色为 $2$ 的袜子。
3. 从抽屉中取出一只颜色为 $1$ 的袜子。此时已经取出的袜子中有 $2$ 只颜色为 $1$ 的袜子和 $1$ 只颜色为 $2$ 的袜子，可以组成一对颜色为 $1$ 的袜子，操作结束。

在这个例子中，高桥君取袜子的次数为 $3$ 次。

高桥君取袜子的次数有 $\frac{2}{3}$ 的概率为 $3$ 次，有 $\frac{1}{3}$ 的概率为 $2$ 次，所以期望值为 $3 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod{998244353}$。

由 ChatGPT 4.1 翻译