AT_abc326_e [ABC326E] Revenge of "The Salary of AtCoder Inc."

题目描述

青木是 AtCoder 公司的员工，他本月的工资通过一个整数 $N$ 和一个长度为 $N$ 的数列 $A$ 按如下方式决定。

首先，青木会得到一个有 $N$ 个面的骰子（每个面上分别标有 $1$ 到 $N$ 的整数，掷出每个面的概率相等），以及一个变量 $x=0$。

然后，重复以下步骤直到结束：

• 掷一次骰子，掷出的点数记为 $y$。
  • 如果 $x < y$，则发放 $A_y$ 日元，并将 $x$ 更新为 $y$。
  • 否则，流程结束。

青木本月的工资为通过上述流程累计发放的金额之和。

请计算青木本月工资的期望值，并对 $998244353$ 取模后输出。

期望值 $\bmod{998244353}$ 的定义
本题中要求的期望值一定是有理数。在本题的约束下，设期望值为最简分数 $\frac{y}{x}$，保证 $x$ 不会被 $998244353$ 整除。此时，存在唯一的 $0 \leq z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，请输出 $z$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
3 2 6

输出 #1

776412280

输入输出样例 #2

输入 #2

1
998244352

输出 #2

998244352

输入输出样例 #3

输入 #3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

输出 #3

545252774

说明/提示

数据范围

• 输入均为整数。
• $1 \leq N \leq 3 \times 10^5$
• $0 \leq A_i < 998244353$

样例解释 1

一种流程如下：

• 初始时，$x=0$。
• 掷一次骰子，结果为 $1$。由于 $0 < 1$，发放 $A_1=3$ 日元，$x$ 更新为 $1$。
• 再掷一次骰子，结果为 $3$。由于 $1 < 3$，发放 $A_3=6$ 日元，$x$ 更新为 $3$。
• 再掷一次骰子，结果为 $1$。由于 $3 \geq 1$，流程结束。

在这个例子中，青木本月的工资为 $9$ 日元。
本月工资的期望值可以计算为 $\frac{49}{9}$ 日元，模 $998244353$ 意义下为 $776412280$。

由 ChatGPT 4.1 翻译