← 返回题目列表

Codeforces · 1349/D

D. 史莱姆和饼干

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

史莱姆和他的 $$$n$$$ 朋友正在参加聚会。史莱姆设计了一款游戏供他的朋友们玩。

游戏开始时,第 $$$i$$$ 位玩家拥有 $$$a_i$$$ 饼干。每一秒,史莱姆会在所有 $$$a_1 + a_2 + \ldots + a_n$$$ 饼干中随机均匀地选择一块饼干,而这块饼干的拥有者会将其送给除自己之外的 $$$n-1$$$ 玩家中的随机统一玩家。当一个人拿走所有饼干时,游戏结束。

作为聚会的主持人,史莱姆想知道游戏将持续的时间的预期值,以便按时举行下一个活动。

为了方便起见,由于互质 $$$p$$$ 和 $$$q$$$ 的答案可以表示为有理数 $$$\frac{p}{q}$$$,因此您需要找到 $$$(p \cdot q^{-1})\mod 998\,244\,353$$$ 的值。你可以证明 $$$q\mod 998\,244\,353 \neq 0$$$。

输入

第一行包含一个整数 $$$n\ (2\le n\le 100\,000)$$$:玩游戏的人数。

第二行包含$$$n$$$非负整数$$$a_1,a_2,\dots,a_n\ (1\le a_1+a_2+\dots+a_n\le 300\,000)$$$,其中$$$a_i$$$表示第$$$i$$$人一开始拥有的饼干数量。

输出

打印一个整数:游戏持续时间的预期值,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

2
1 1

输出 #1

1

输入 #2

2
1 2

输出 #2

3

输入 #3

5
0 0 0 0 35

输出 #3

0

输入#4

5
8 4 2 0 1

输出#4

801604029

注意

对于第一个例子,在第一秒,玩家$$$1$$$给玩家$$$2$$$一块饼干的概率是$$$\frac{1}{2}$$$,而玩家$$$2$$$给玩家$$$1$$$一块饼干的概率是$$$\frac{1}{2}$$$。但无论如何,游戏将在 $$$1$$$ 秒后停止,因为在 $$$1$$$ 秒后只有一名玩家会占据所有饼干,所以答案是 $$$1$$$。