← 返回题目列表

Codeforces · 1479/E

E. 学校俱乐部

中文机器翻译题面 查看原题

在荷马的学校里,有$$$n$$$ 的学生热爱俱乐部。

最初,有 $$$m$$$ 个俱乐部,并且每个 $$$n$$$ 学生都属于一个俱乐部。换句话说,第 $$$i$$$ 俱乐部中有 $$$a_i$$$ 学生,$$$1 \leq i \leq m$$$ 和 $$$a_1+a_2+\dots+a_m = n$$$。

$$$n$$$ 学生非常不友好,以至于每天他们中的一个(从所有 $$$n$$$ 学生中随机选择的)都会生气。生气的学生会做以下事情之一。

- 以 $$$\frac 1 2$$$ 的概率,他离开当前的俱乐部,然后自己创建一个新俱乐部并加入它。他创建的新社团里只有一名学生(他自己)。
- 以 $$$\frac 1 2$$$ 的概率,他不会创建新俱乐部。在这种情况下,他将他的俱乐部更换为一个新俱乐部(可能是他当前所在的同一俱乐部),其概率与该俱乐部中的学生数量成正比。正式地,假设有 $$$k$$$ 俱乐部,并且第 $$$i$$$ 俱乐部中有 $$$b_i$$$ 学生,$$$1 \leq i \leq k$$$ (在学生生气之前)。他离开当前的俱乐部,然后以 $$$\frac {b_i} {n}$$$ 的概率加入第 $$$i$$$ 个俱乐部。

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$$$ 为模。

示例

输入 #1

2
1 1

输出 #1

4

输入 #2

2
1 2

输出 #2

18

输入 #3

3
1 1 1

输出 #3

21

输入#4

1
400000000

输出#4

0

输入 #5

10
1 2 3 4 5 6 7 8 9 10

输出 #5

737609878

注意

在第一个例子中,无论哪个学生生气,这两个学生都会以 $$$\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$$$。