No.2875 What is My Rank?
タグ : / 解いたユーザー数 50
作問者 :
寝癖
/ テスター :
👑 
seekworser
yuusaan
Problem Statement
Neguse-kun participated in a marathon-style contest.
This contest had $N$ participants including Neguse-kun, and the $1$-st participant is Neguse-kun.
In the contest, it is known that the $i\ (1\le i \le N)$-th participant obtains a score that is an integer between $l_i$ and $r_i$, inclusive, with each value being equally likely.
After the contest ends, ranks are assigned in descending order of score, and in case of a tie, the person with the smaller number gets the higher rank.
Find the expected value of Neguse-kun's rank, $\rm mod 998244353$.
Definition of expected value $\bmod \ 998244353$
It can be proved that the expected value sought in this problem is always a rational number. Also, under the constraints of this problem, when the probability sought is represented as an irreducible fraction $\frac{y}{x}$, there uniquely exists an integer $0 \le z < 998244353$ such that $xz \equiv y \quad ( \bmod \ 998244353 )$. Output this $z$.Input
$N$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_N\ r_N$
Constraints
- $1\le N \le 2\times 10^5$
- $1\le l_i \le r_i \le 10^9,\ i=1,2,\dots,N$
- $r_i-l_i+1\neq 998244353,\ i=1,2,\dots,N$
- All inputs are integers.
Output
Output the expected value of Neguse-kun's rank, $\rm mod 998244353$, on one line.
Sample
Sample 1
Input
3 5 5 1 2 5 7
Output
665496237
The scores of persons $1,2,3$ have $6$ possibilities, $(5,1,5),(5,1,6),(5,1,7),(5,2,5),(5,2,6),(5,2,7)$, and each of them occurs with equal probability.
Neguse-kun's ranks are $1,2,2,1,2,2$ respectively, so the expected value of the rank is $\frac{1+2+2+1+2+2}{6}=\frac{5}{3}$.
Sample 2
Input
1 1 1
Output
1
Sample 3
Input
4 1 10 1 10 1 10 1 10
Output
49912220
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。