問題一覧 > 通常問題

No.2336 Do you like typical problems?

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

問題文

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

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

入力

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

NN
B1B_1 C1C_1
B2B_2 C2C_2
⋮\vdots
BNB_N CNC_N

出力

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

制約

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

  • 1≤N≤200 0001 \leq N \leq 200\,000
  • 1≤Bi≤Ci<998 244 353 (1≤i≤N)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]p=[1,2] のとき、転倒数の期待値は 19\displaystyle{\cfrac{1}{9}} です。
p=[2,1]p=[2,1] のとき、転倒数の期待値は 23\displaystyle{\cfrac{2}{3}} です。
よって、期待値の総和は 79\displaystyle{\cfrac{7}{9}} となります。
7−9×110 916 040=−998 244 3537 - 9 \times 110\,916\,040 = -998\,244\,353 は 998 244 353998\,244\,353 の倍数なので、110 916 040110\,916\,040 を出力します。

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

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

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

期待値の総和は 00 です。

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