← 返回题目列表

AtCoder · abc463_f

F. 千竹乐

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

分数: 500 点

问题陈述

一场锦标赛正在举行 2N 玩家。 从现在开始,每位球员将只踢一场比赛。 在剩余的 N 匹配, i-th (1\le i\le N) 比赛在 (2i-1)-th 和 2i第玩家。

在每场比赛中,两名参赛者中一名获胜,另一名失败。 哪位玩家获胜是每场比赛独立确定的,每个玩家获胜的概率 \dfrac12.

最后之前 N 比赛开始, i-th (1\le i\le2N) 玩家获胜 A _ i 次。 所有比赛结束后,从获胜次数最多的选手中随机选出冠军,与之前的比赛结果无关。

对于第一、第二个中的每一个, \ldots, 2N-th 玩家,求概率,取模 998244353,该玩家成为冠军。

概率模的定义 998244353

可以证明,求的概率总是有理数。而且,在这个问题的约束下,可以证明,当有理数表示为不可约分数时 \frac{P}{Q},我们有 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,存在一个唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353。找到这个 R.

约束

  • 1\le N\le2\times10 ^ 5
  • 0\le A _ i\lt2N\ (1\le i\le 2N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A _ 1 A _ 2
A _ 3 A _ 4
\vdots
A _ {2N-1} A _ {2N}

输出

输出第一个玩家成为冠军的概率,第二个玩家成为冠军的概率, \ldots,概率 2N第一个成为冠军的玩家,按此顺序,以空格分隔,在一行上。


示例输入 1

4
1 2
3 4
2 3
1 4

示例输出 1

0 0 259959467 883862188 0 967049217 0 883862188

例如,在以下情况下,第三位玩家成为冠军:

  • 如果第三名选手在第二场比赛中获胜,第五名选手在第三场比赛中获胜,并且第七名选手在第四场比赛中获胜,则第三名选手有概率成为冠军 \dfrac13.
  • 如果第三名选手在第二场比赛中获胜,第六名选手在第三场比赛中获胜,并且第七名选手在第四场比赛中获胜,则第三名选手有概率成为冠军 \dfrac14.

因此,第三位选手成为冠军的概率为 \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}。我们有 259959467\times96\equiv7\pmod{998244353},因此第三位玩家成为冠军的概率取模 -998244353 表达式为 259959467.

每个玩家成为冠军的概率为 0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}。 因此,输出 0 0 259959467 883862188 0 967049217 0 883862188.


示例输入 2

6
0 0
0 0
0 0
0 0
0 0
0 0

示例输出 2

582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206

可能还没有人获胜。

根据对称性,每个玩家都有概率成为冠军 \dfrac1{12}.


示例输入 3

10
18 17
16 18
18 16
16 16
17 17
16 16
17 16
17 18
16 16
17 18

示例输出 3

357877533 151989635 0 357877533 357877533 0 0 0 575116994 575116994 0 0 597386855 0 151989635 357877533 0 0 151989635 357877533