Affine Sort

AtCoder

IDarc126_f

Time5000ms

Memory256MB

Difficulty—

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). ## 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$ [samples] ## 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$.

Samples

Input #1

3
3 1 2

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}$.

Input #2

3
5 9 2

Output #2

832860616

We have $\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008}$ .

Input #3

2
2 3

Output #3

166374059

We have $\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6}$.

Input #4

4
4 5 3 2

Output #4

0

We have $\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0$.

API Response (JSON)

{
  "problem": {
    "name": "Affine Sort",
    "description": {
      "content": "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 cond",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc126_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a sequence of $N$ positive integers $X = (X_1, X_2, \\ldots, X_N)$.\nFor a positive integer $K$, let $f(K)$ be the number of triples of integers $(a,b,c)$ that satisfy all of the following cond...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments