Revenge of "The Salary of AtCoder Inc."

题目描述

Aoki，AtCoder 株式会社的一名员工，本月的工资由整数 $N$ 和长度为 $N$ 的序列 $A$ 决定，规则如下。
首先，给他一个 $N$ 面的骰子（骰子）且每个面显示 $1$ 到 $N$ 的整数，概率相等，并且有一个变量 $x=0$ 。然后反复执行以下步骤直到终止。

掷一次骰子，记结果为 $y$ 。如果 $x<y$ ，则支付他 $A_y$ 日元并令 $x=y$ 。否则，终止该过程。

Aoki 本月的工资是通过该过程支付的总额。
求 Aoki 本月工资的期望值，模 $998244353$ 。

如何对 $998244353$ 取模求期望值

可以证明本题中要求的期望值总是有理数。并且，本题约束保证如果将所求期望值表示为最简分数 $\frac yx$ ，那么 $x$ 不被 $998244353$ 整除。

在这里存在唯一的 $0\leq z\lt998244353$ 使得 $y\equiv xz\pmod{998244353}$ 。输出这个 $z$ 。

输入按下述格式由标准输入提供： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出答案。

3
3 2 6

776412280

1
998244352

998244352

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

545252774

所有输入都是整数。 $1 \le N \le 3 \times 10^5$ $0 \le A_i < 998244353$ 下面是该过程如何进行的一个例子。

最初， $x=0$ 。掷一次骰子，结果为 $1$ 。由于 $0<1$ ，支付他 $A_1 = 3$ 日元并令 $x=1$ 。掷一次骰子，结果为 $3$ 。由于 $1<3$ ，支付他 $A_3 = 6$ 日元并令 $x=3$ 。掷一次骰子，结果为 $1$ 。由于 $3 \ge 1$ ，过程终止。

在这个例子中，他本月的工资是 $9$ 日元。可以计算出他本月工资的期望值是 $\frac{49}{9}$ 日元，其在模 $998244353$ 下的表示是 $776412280$ .

标签: AtCoder|abc326E

AtCoder|abc326E