/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
N 項からなる正整数列 X = (X_1, X_2, \ldots, X_N) が与えられます。
正の整数 K に対して、整数の組 (a,b,c) のうちで以下の条件がすべて成り立つものの個数を f(K) と書くことにします。
- 1\leq c \leq K
- 0\leq a < c かつ 0\leq b < c
- 各 i に対して aX_i + b を c で割った余りを Y_i とするとき、Y_1 < Y_2 < \cdots < Y_N が成り立つ。
極限 \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} が存在することが証明できます。 この値を \mod 998244353 で求めてください（注記参照）。
注記
求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R\times Q\equiv P\pmod{998244353} かつ 0\leq R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 2\leq N\leq 10^3
- X_i は正の整数で、\sum_{i=1}^N X_i \leq 5\times 10^5 を満たす
- i\neq j ならば X_i\neq X_j
入力
入力は以下の形式で標準入力から与えられます。
N X_1 X_2 \ldots X_N
出力
\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} を \mod 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 が成り立ちます。
Score : 1100 points
Problem Statement
Given is a sequence of N positive integers X = (X_1, X_2, \ldots, X_N).
For a positive integer K, let f(K) be the number of triples of integers (a,b,c) that satisfy all of the following conditions.
- 1\leq c \leq K.
- 0\leq a < c and 0\leq b < c.
- For each i, let Y_i be the remainder when aX_i + b is divided by c. Then, Y_1 < Y_2 < \cdots < Y_N holds.
It can be proved that the limit \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} exists. Find this value modulo 998244353 (see Notes).
Notes
We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as \frac{P}{Q} using two coprime integers P and Q, we can prove that there is a unique integer R such that R\times Q\equiv P\pmod{998244353} and 0\leq R < 998244353. Find this R.
Constraints
- 2\leq N\leq 10^3
- X_i are positive integers such that \sum_{i=1}^N X_i \leq 5\times 10^5.
- X_i\neq X_j if i\neq j.
Input
Input is given from Standard Input in the following format:
N X_1 X_2 \ldots X_N
Output
Print \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} modulo 998244353.
Sample Input 1
3 3 1 2
Sample Output 1
291154603
- For example, when (a,b,c) = (3,5,7), we have Y_1 = 0, Y_2 = 1, Y_3 = 4, which satisfy Y_1 < Y_2 < Y_3.
- We have f(1) = 0, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 5.
- We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{24}.
Sample Input 2
3 5 9 2
Sample Output 2
832860616
We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008} .
Sample Input 3
2 2 3
Sample Output 3
166374059
We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6}.
Sample Input 4
4 4 5 3 2
Sample Output 4
0
We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0.