分数: 575 点
问题陈述
给你一个序列 A of N 非负整数。
重复以下操作,直到 A 仅有一个元素。
- 选择两个不同的整数 i 和 j 满意 1 \leq i, j \leq |A| 均匀随机。
- 让 a 和 b be A_i 和 A_j。
- 删除 i-th 和 j- 第一个元素来自 A.
- 追加 a - b 到年底 A.
让 x 是唯一的元素 A 在最后。 求出期望值 x^2,模数 998244353.
期望值模的定义 998244353
可以证明,要找到的期望值总是有理数。还可以证明,在该问题的约束下,当表示为不可约分数时 \frac{P}{Q},我们有 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,有一个唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。找到这个 R.
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 998244352
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
在一行上输出答案。
示例输入 1
3 4 5 0
示例输出 1
665496263
首先,选择 (i, j) = (3, 1) 使序列 (5, -4).
接下来,选择 (i, j) = (1, 2) 使序列 (9).
x^2 等于 81 有概率 \frac{1}{3} 和 1 有概率 \frac{2}{3},所以期望值为 \frac{83}{3}.
示例输入 2
5 450 2026 3 21 100
示例输出 2
669406799