随机减法AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a sequence $A$ of $N$ non-negative integers.
Repeat the following operation until $A$ has exactly one element.
- Choose two distinct integers
$i$and$j$satisfying$1 \leq i, j \leq |A|$uniformly at random. - Let
$a$and$b$be$A_i$and$A_j$, respectively. - Remove the
$i$-th and$j$-th elements from$A$. - Append
$a - b$to the end of$A$.
Let $x$ be the only element of $A$ at the end. Find the expected value of $x^2$, modulo $998244353$.
Definition of expected value modulo $998244353$ It can be proved that the expected value to be found is always a rational number. It can also be proved that under the constraints of this problem, when expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Thus, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Find this $R$.
给定一个由 $N$ 个非负整数构成的序列 $A$。
重复执行以下操作，直到 $A$ 恰好只剩一个元素。
- 在满足
$1 \leq i, j \leq |A|$且$i \ne j$的整数中，等概率随机选择两个整数$i$和$j$。 - 令
$a$和$b$分别为$A_i$和$A_j$。 - 从
$A$中删除第$i$个和第$j$个元素。 - 将
$a - b$添加到$A$的末尾。
设操作结束时 $A$ 中唯一的元素为 $x$。求 $x^2$ 的期望值对 $998244353$ 取模后的结果。
期望值对 $998244353$ 取模的定义
可以证明，所求的期望值一定是有理数。还可以证明，在本题的约束条件下，将其表示为最简分数 $\frac{P}{Q}$ 时，有 $Q {{}\not\equiv{}} 0 \pmod{998244353}$。因此，满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$ 的整数 $R$ 唯一存在。请求出这个 $R$。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \leq N \leq 2 \times 10^5$$0 \leq A_i \leq 998244352$- All input values are integers.
$1 \leq N \leq 2 \times 10^5$$0 \leq A_i \leq 998244352$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
A_1 A_2 \dots A_NN
A_1 A_2 \dots A_NOutput
输出格式
AI (CI翻译)Output the answer on a single line.
在一行中输出答案。AI (CI翻译)
样例
3
4 5 0
665496263
5
450 2026 3 21 100
669406799
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。