Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 枚のカードがあります。それぞれのカードには 1 から N の番号がつけられています。blackyuki 君と KoD 君はこのカードを使ってゲームをすることにしました。
blackyuki 君から初めて、全てのカードがなくなるまで交互に以下の操作を繰り返します。
- 残っているカードから 1 枚選ぶ、選んだカードの番号を i とする。
- \frac{A_i}{B_i} の確率でカード i を手に入れ、操作の初めに戻る。
- 1-\frac{A_i}{B_i} の確率で、何もせず操作を終了する。
ゲーム終了時に blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であれば blackyuki 君の勝ち、そうでなければ KoD 君の勝ちとします。
2 人は、以下のように行動します。
- まず、自分がゲーム終了時に持っているカードの枚数の期待値を最大化するようにカードを選ぶ。
- 上記のみでは選ぶカードの候補が複数ある場合、その中で最も番号が小さいカードを選ぶ。
blackyuki 君の勝つ確率 \bmod\ 998244353 を求めてください。
注記
求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P,Q を用いて \frac{P}{Q} と表した時、R \times Q \equiv P(\bmod\ 998244353) かつ 0 \le R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 入力は全て整数である。
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le B_i \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを 1 行に出力せよ。
入力例 1
1 1 2
出力例 1
665496236
カード 1 を選び続けるしかありません。blackyuki 君がカード 1 を手に入れる確率は \frac{2}{3} です。
入力例 2
2 1 1 1 1
出力例 2
1
初めに、blackyuki 君がカード 1 を選んだとします。\frac{A_1}{B_1}=1 なので、カード 1 を必ず取ることができます。
そして、blackyuki 君は次にカード 2 を選ぶしかありません。\frac{A_2}{B_2}=1 なので、カード 2 も必ず取ることができます。
ゲーム終了時において、必ず blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であるため、1 を出力します。
入力例 3
8 100660 113169 10964 152336 57329 77239 98640 167660 103515 136455 98695 99571 14421 149410 12488 21041
出力例 3
743177673