← 返回题目列表

AtCoder · arc126_f

F. 仿射排序

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

分数: 1100 点

问题陈述

给定的是一系列 N 正整数 X = (X_1, X_2, \ldots, X_N).

对于正整数 K,让 f(K) 是整数三元组的数量 (a,b,c) 满足以下所有条件。

  • 1\leq c \leq K.
  • 0\leq a < c 和 0\leq b < c.
  • 对于每个 i,让 Y_i 为余数 aX_i + b 除以 c。然后, Y_1 < Y_2 < \cdots < Y_N 成立。

可以证明极限 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} 存在。求这个值的模 998244353 (见注释)。

注释

我们可以证明所讨论的极限始终是有理数。此外,在这个问题的约束下,当该数字表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,我们可以证明有一个唯一的整数 R 这样 R\times Q\equiv P\pmod{998244353} 和 0\leq R < 998244353。找到这个 R.

约束

  • 2\leq N\leq 10^3
  • X_i 是正整数,使得 \sum_{i=1}^N X_i \leq 5\times 10^5.
  • X_i\neq X_j if i\neq j.

输入

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

N
X_1 X_2 \ldots X_N

输出

打印 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} 模数 998244353.


示例输入 1

3
3 1 2

示例输出 1

291154603
  • 例如,当 (a,b,c) = (3,5,7),我们有 Y_1 = 0, Y_2 = 1, Y_3 = 4,满足 Y_1 < Y_2 < Y_3.
  • 我们有 f(1) = 0, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 5.
  • 我们有 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{24}.

示例输入 2

3
5 9 2

示例输出 2

832860616

我们有 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008} .


示例输入 3

2
2 3

示例输出 3

166374059

我们有 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6}.


示例输入 4

4
4 5 3 2

示例输出 4

0

我们有 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0.