AT_jsc2024_final_a.Random Descents

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\cdots,A_N)$。定义 $S = \sum_{1 \leq i \leq N} A_i$。

长度为 $S$ 的整数序列 $x$ 满足以下全部条件时（且仅当如此），称为“good”：

• $x$ 的每个元素均在 $1$ 到 $N$ 之间；
• 对于每个整数 $i$（$1 \leq i \leq N$），$x$ 恰好包含 $A_i$ 个 $i$。

对于整数序列 $x=(x_1,x_2,\cdots,x_S)$，记满足 $x_i > x_{i+1}$ 的下标 $i$ 的个数为 $f(x)$。

从所有“good”的整数序列 $x$ 中等概率随机选取一个，求 $f(x)$ 的期望，结果对 $998244353$ 取模。

期望值 $\bmod{998244353}$ 定义如下：可以证明要计算的期望一定是有理数，并且在本题的约束下，若将期望表示为最简分数 $\frac{P}{Q}$，有 $Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$。请输出该整数 $R$。

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

$N\ A_1\ A_2\ \cdots\ A_N$

输出答案。

样例解释 1

“good” 的 $x$ 有 $3$ 种：

• $x=(1,2,2)$，$f(x)=0$
• $x=(2,1,2)$，$f(x)=1$
• $x=(2,2,1)$，$f(x)=1$

因此 $f(x)$ 的期望为 $2/3$。

数据范围

• $2 \leq N \leq 250000$
• $1 \leq A_i$
• $\sum_{1 \leq i \leq N} A_i < 998244353$
• 所有输入均为整数。

由 ChatGPT 5 翻译