問題一覧 > 通常問題

No.2336 Do you like typical problems?

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 68
作問者 : SSRS / テスター : 👑 hamamu 👑 Nachia
お気に入りにしたユーザー ProblemId : 6703 / 自分の提出
問題文最終更新日: 2023-06-01 12:17:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 391 (順位表) の他の問題:

Problem Statement

E869120 created the following problem.

Various Arrays
Takahashi, a sequence maker, is creating a sequence $a$ of length $N$.
The $i$-th element ($1 \leq i \leq N$) of the sequence $a$ is determined by choosing uniformly at random from the integers between $L_i$ and $R_i$, inclusive.
Find the expected value of the inversion number of the sequence $a$ created in this way.
Here, the inversion number of the sequence $a$ is the number of pairs of integers $i, j$ such that $1 \leq i < j \leq N$ and $a_i > a_j$.
Since this problem was too easy for SSRS, he decided to find the sum of the answers to Various Arrays with $L_i=B_{p_i}, R_i=C_{p_i}$, over all permutations $p_1,p_2,\cdots,p_N$ of $1,2,\dots,N$.
It can be proved that the sum can be expressed as $\displaystyle{\cfrac{x}{y}}$ using coprime integers $x,y$, and that there exists exactly one $z$ with $0 \leq z \lt 998\,244\,353$ such that $x-yz$ is a multiple of $998\,244\,353$. Find the value of $z$.

Input

The input is given from standard input in the following format.

$N$
$B_1$ $C_1$
$B_2$ $C_2$
$\vdots$
$B_N$ $C_N$

Output

Print the value of $z$ to standard output in $1$ line.
Print a newline at the end.

Constraints

The input satisfies the following constraints.

  • $1 \leq N \leq 200\,000$
  • $1 \leq B_i \leq C_i < 998\,244\,353 \ (1 \leq i \leq N)$
  • All input values are integers.

Sample

Sample 1
Input
2
1 3
2 4
Output
110916040

When $p=[1,2]$, the expected value of the inversion number is $\displaystyle{\cfrac{1}{9}}$.
When $p=[2,1]$, the expected value of the inversion number is $\displaystyle{\cfrac{2}{3}}$.
Therefore, the sum of the expected values is $\displaystyle{\cfrac{7}{9}}$.
Since $7 - 9 \times 110\,916\,040 = -998\,244\,353$ is a multiple of $998\,244\,353$, print $110\,916\,040$.

Sample 2
Input
4
1 5
2 9
7 10
3 4
Output
823551657

The sum of the expected values is $\displaystyle{\cfrac{2\,631}{40}}$.

Sample 3
Input
1
1 998244352
Output
0

The sum of the expected values is $0$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。