← 返回题目列表

AtCoder · jsc2024_final_a

A. 随机下降

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

配点 : 300 点

問題文

长度 N 的正整数序列 给出了 A=(A_1,A_2,\cdots,A_N) 。 从此, 比方说S=\sum_{1 \leq i \leq N} A_i 。

长度 S 整数序列 x 当(且仅当)满足以下所有条件时: 我们说好 。

  • 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) 。

好的整数序列 当 x 随机均匀取时, f(x) 的预期值为 使用 \pmod{998244353} 找到它。

期待値 \pmod{998244353} 的定义

可以证明期望的期望值始终是有理数。另外,在这个问题的约束下,我们可以将该值转换为不可约分数 当表示为 \frac{P}{Q} 时, 也可以证明Q \neq 0 \pmod{998244353} 。因此, 满足R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 的整数 R 是唯一确定的。这个 请回答 R 。

制約

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

入力

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

N
A_1 A_2 \cdots A_N

出力

打印答案。


入力例 1

2
1 2

出力例 1

665496236

好 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

5
1 1 1 1 1

出力例 2

2

入力例 3

2
2024 824

出力例 3

841217737

入力例 4

10
19237224 3435339 227368010 836006 153314679 115537801 189694444 76016030 159566203 53238564

出力例 4

873203747