CF1479E School Clubs

在 Homer 的学校里，有 $n$ 个喜欢社团的学生。 最初有 $m$ 个社团，每个学生恰好属于一个社团。换句话说，第 $i$ 个社团有 $a_i$ 个学生，$1 \leq i \leq m$，并且 $a_1+a_2+\dots+a_m = n$。 这些学生非常不友好，每天会有一个学生（从所有 $n$ 个学生中等概率随机选择）生气。生气的学生会做以下两件事之一： - 以概率 $\frac{1}{2}$，他会离开当前社团，然后自己新建一个社团并加入。新建的社团只有他自己一个人。 - 以概率 $\frac{1}{2}$，他不会新建社团。在这种情况下，他会以与各社团人数成比例的概率选择一个社团（可能是他当前所在的社团）加入。具体来说，假设当前有 $k$ 个社团，第 $i$ 个社团有 $b_i$ 个学生（在该学生生气之前），那么他会离开当前社团，然后以概率 $\frac{b_i}{n}$ 加入第 $i$ 个社团。 注意，当某个社团人数变为 $0$ 时，学生们不会再加入这个社团，因为根据上述规则，生气的学生加入空社团的概率为 $0$。 Homer 想知道，期望经过多少天后，所有学生第一次全部在同一个社团中。 可以证明，答案可以表示为一个最简分数 $\frac{p}{q}$，其中 $\gcd(p, q) = 1$。因此，你需要输出 $pq^{-1} \bmod 998\,244\,353$ 的值。可以证明，在题目给定的约束下，$q \bmod 998\,244\,353 \neq 0$。

第一行包含一个整数 $m$（$1 \leq m \leq 1000$）——最初的社团数量。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \leq a_i \leq 4 \cdot 10^8$），且 $1 \leq a_1+a_2+\dots+a_m \leq 4 \cdot 10^8$，其中 $a_i$ 表示第 $i$ 个社团最初的人数。

输出一个整数，表示所有学生第一次全部在同一个社团中的期望天数，结果对 $998\,244\,353$ 取模。

在第一个样例中，无论哪个学生生气，两名学生变成同一个社团的概率都是 $\frac{1}{4}$。所以期望天数为 $4$。 在第二个样例中，第一天的情况如下： - 第一个社团的唯一学生生气的概率为 $\frac{1}{3}$。如果他生气，他以概率 $\frac{1}{2}$ 新建社团（此时有三个社团，人数分别为 $0, 1, 2$），以概率 $\frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}$ 离开当前社团并加入第二个社团，或者以概率 $\frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}$ 保持不变； - 第二个社团的每个学生生气的概率为 $\frac{1}{3}$。如果其中一人生气，他以概率 $\frac{1}{2}$ 新建社团，以概率 $\frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}$ 离开当前社团并加入第二个社团，或者以概率 $\frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}$ 保持不变。 在第四个样例中，最初只有一个社团，即所有学生已经在同一个社团，所以答案为 $0$。 由 ChatGPT 4.1 翻译