AT_abc270_h [ABC270Ex] add 1

题目描述

给定一个 $N$ 个非负整数的序列 $A=(A_1,A_2,\ldots,A_N)$，满足 $A_1=0$ 且 $A_N>0$。

高桥君有 $N$ 个计数器，初始时所有计数器的值均为 $0$。
高桥君会不断进行如下操作，直到对于所有 $1\leq i\leq N$，第 $i$ 个计数器的值都达到 $A_i$ 及以上为止：

从 $N$ 个计数器中等概率随机选择一个，将其值重置为 $0$。（每次选择相互独立。）
除被选中的计数器外，其余所有计数器的值都加 $1$。

请输出高桥君操作次数的期望值，结果对 $998244353$ 取模（见注记）。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出高桥君操作次数的期望值，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2
0 2

输出 #1

6

输入输出样例 #2

输入 #2

5
0 1 3 10 1000000000000000000

输出 #2

874839568

说明/提示

注记

可以证明，所求的期望值一定是有限的有理数。在本题的约束下，设该值可表示为互质的两个整数 $P$、$Q$ 之比 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R<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$
• 输入均为整数

样例解释 1

用 $C_i$ 表示第 $i$ 个计数器的当前值。高桥君操作至所有计数器达到目标值的一个可能过程如下：

• 将第 $1$ 个计数器重置为 $0$，其余计数器加 $1$，此时 $(C_1,C_2)=(0,1)$。
• 将第 $2$ 个计数器重置为 $0$，其余计数器加 $1$，此时 $(C_1,C_2)=(1,0)$。
• 将第 $1$ 个计数器重置为 $0$，其余计数器加 $1$，此时 $(C_1,C_2)=(0,1)$。
• 将第 $1$ 个计数器重置为 $0$，其余计数器加 $1$，此时 $(C_1,C_2)=(0,2)$。

此时操作次数为 $4$。在第 $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$。

由 ChatGPT 4.1 翻译