No.2336 Do you like typical problems?
Problem Statement
E869120 created the following problem.
Various ArraysSince 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$.
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$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
hamamu
Nachia