← 返回题目列表

AtCoder · abc450_g

G. 随机减法

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

分数: 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