分数: 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.