問題一覧 > 通常問題

No.2875 What is My Rank?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : 寝癖 / テスター : 👑 seekworser yuusaan
2 ProblemId : 11167 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-06 21:46:10

問題文

寝癖くんはあるマラソン型コンテストに参加しました。

このコンテストは寝癖くんを含めて NN 人の人が参加したものであり、11 番目の参加者が寝癖くんです。

コンテストにおいて、i (1≤i≤N)i\ (1\le i \le N) 番目の参加者は lil_i 点以上 rir_i 点以下の整数値のスコアをそれぞれ等確率で取ることがわかっています。

また、コンテストの終了後には、スコアの大きい順に順位がつけられ、同点の場合は番号の若い人が高順位になります。

寝癖くんの順位の期待値を mod998244353\rm mod 998244353 で求めてください。

期待値  mod  998244353\bmod \ 998244353 の定義 この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 yx\frac{y}{x} で表したときに xz≡y( mod  998244353)xz \equiv y \quad ( \bmod \ 998244353 ) を満たすような整数 0≤z<9982443530 \le z < 998244353 が一意に定まります。この zz を答えてください。

入力

NN
l1 r1l_1\ r_1
l2 r2l_2\ r_2
⋮\vdots
lN rNl_N\ r_N

制約

  • 1≤N≤2×1051\le N \le 2\times 10^5
  • 1≤li≤ri≤109, i=1,2,…,N1\le l_i \le r_i \le 10^9,\ i=1,2,\dots,N
  • ri−li+1≠998244353, i=1,2,…,Nr_i-l_i+1\neq 998244353,\ i=1,2,\dots,N
  • 入力はすべて整数

出力

寝癖くんの順位の期待値 mod998244353\rm mod 998244353 を一行で出力してください。

サンプル

サンプル1
入力
3
5 5
1 2
5 7
出力
665496237

人 1,2,31,2,3 のスコアは (5,1,5),(5,1,6),(5,1,7),(5,2,5),(5,2,6),(5,2,7)(5,1,5),(5,1,6),(5,1,7),(5,2,5),(5,2,6),(5,2,7) の 66 通りあり、どの場合も等確率で起こり得ます。

寝癖くんの順位はそれぞれ 1,2,2,1,2,21,2,2,1,2,2 となるので順位の期待値は 1+2+2+1+2+26=53\frac{1+2+2+1+2+2}{6}=\frac{5}{3} です。

サンプル2
入力
1
1 1
出力
1
サンプル3
入力
4
1 10
1 10
1 10
1 10
出力
49912220

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