← 返回题目列表

AtCoder · abc270_h

Ex. 添加1

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

分数: 600 点

问题陈述

给你一个元组 N 非负整数 A=(A_1,A_2,\ldots,A_N) 这样 A_1=0 和 A_N>0.

高桥有 N 计数器。最初,所有计数器的值是 0.
他会重复下面的操作,直到对于每一个 1\leq i\leq N,值 i-th 计数器至少 A_i.

选择其中一项 N 随机均匀计数,并将其值设置为 0。 (每个选择都独立于其他选择。)
增加值 其他 计数器按 1.

打印 Takahashi 重复运算次数的期望值,取模 998244353 (见注释)。

注释

可以证明,所求的期望值总是有限且有理的。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,可以证明存在唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.

约束

  • 2\leq N\leq 2\times 10^5
  • 0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}
  • A_N>0
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印 Takahashi 重复运算次数的期望值,取模 998244353.


示例输入 1

2
0 2

示例输出 1

6

让 C_i 表示的值 i第一个计数器。

这是该过程的一种可能的进展。

  • 设置的值 1-st 计数器 0,然后将另一个计数器的值增加 1。现在, (C_1,C_2)=(0,1).
  • 设置的值 2-nd 计数器 0,然后将另一个计数器的值增加 1。现在, (C_1,C_2)=(1,0).
  • 设置的值 1-st 计数器 0,然后将另一个计数器的值增加 1。现在, (C_1,C_2)=(0,1).
  • 设置的值 1-st 计数器 0,然后将另一个计数器的值增加 1。现在, (C_1,C_2)=(0,2).

在这种情况下,该操作被执行四次。

进程在恰好之后结束的概率 1,2,3,4,5,\ldots 操作是 0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots,因此寻求的期望值是 2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6。 因此, 应打印 6 。


示例输入 2

5
0 1 3 10 1000000000000000000

示例输出 2

874839568