← 返回题目列表

AtCoder · nadafes2022_day1_m

M. 随机绘图

中文机器翻译题面 查看原题

配点 : 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