問題一覧 > 通常問題

No.2336 Do you like typical problems?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : SSRSSSRS / テスター : hamamuhamamu 👑 NachiaNachia
3 ProblemId : 6703 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-01 12:17:02

問題文

E869120 さんは以下の問題を作りました。

Various Arrays
数列屋の高橋くんは長さ $N$ の数列 $a$ を作っています。
数列 $a$ の $i$ 番目 ($1 \leq i \leq N$) の要素は $L_i$ 以上 $R_i$ 以下の整数から一様ランダムに選ぶことで決定されます。
このようにしてできた数列 $a$ の転倒数の期待値を求めてください。
ただし、数列 $a$ の転倒数とは $1 \leq i < j \leq N$ なる整数 $i, j$ の組のうち $a_i > a_j$ となるものの個数のことです。
SSRS さんにとってこの問題は簡単すぎたので、$1,2,\dots,N$ の順列 $p_1,p_2,\cdots,p_N$ すべてについての $L_i=B_{p_i}, R_i=C_{p_i}$ としたときの Various Arrays の答えの総和を求めることにしました。
総和は互いに素な整数 $x,y$ を用いて $\displaystyle{\cfrac{x}{y}}$ と表され、さらに $0 \leq z \lt 998\,244\,353$ なる $z$ で $x-yz$ が $998\,244\,353$ の倍数となるものがただ一つ存在することが証明できます。$z$ の値を求めてください。

入力

入力は以下の形式で標準入力から与えられます。 

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

出力

$z$ の値を標準出力に $1$ 行で出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

  • $1 \leq N \leq 200\,000$
  • $1 \leq B_i \leq C_i < 998\,244\,353 \ (1 \leq i \leq N)$
  • 入力される値はすべて整数である。

サンプル

サンプル1
入力
2
1 3
2 4
出力
110916040

$p=[1,2]$ のとき、転倒数の期待値は $\displaystyle{\cfrac{1}{9}}$ です。
$p=[2,1]$ のとき、転倒数の期待値は $\displaystyle{\cfrac{2}{3}}$ です。
よって、期待値の総和は $\displaystyle{\cfrac{7}{9}}$ となります。
$7 - 9 \times 110\,916\,040 = -998\,244\,353$ は $998\,244\,353$ の倍数なので、$110\,916\,040$ を出力します。

サンプル2
入力
4
1 5
2 9
7 10
3 4
出力
823551657

期待値の総和は $\displaystyle{\cfrac{2\,631}{40}}$ です。

サンプル3
入力
1
1 998244352
出力
0

期待値の総和は $0$ です。

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