F - Senshuraku 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

2N 人の選手が参加する大会が行われています。 これから、それぞれの選手は 1 回試合を行います。 残る N 回の試合のうち、i 番目 (1\le i\le N) の試合では 2i-1 番目の選手と 2i 番目の選手が対戦を行います。

それぞれの試合では、対戦する 2 人の選手のうち 1 人が勝ち、もう 1 人が負けます。 どちらの選手が勝つかは試合ごとに独立に確率 \dfrac12 で決まります。

最後の N 試合が始まる前、i 番目 (1\le i\le2N) の選手は A _ i 回勝っています。 すべての試合が終わったあと、勝った回数が最も多い選手の中から一様ランダムかつこれまでの試合結果と独立に優勝選手が選ばれます。

1 番目の選手、2 番目の選手、\ldots、2N 番目の選手のそれぞれについて、優勝する確率を{}\bmod998244353 で求めてください。

確率{}\bmod{998244353} の定義

求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この 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}

出力

1 番目の選手が優勝する確率、2 番目の選手が優勝する確率、\ldots 、2N 番目の選手が優勝する確率を、この順に空白を区切りとして 1 行に出力せよ。

入力例 1

4
1 2
3 4
2 3
1 4

出力例 1

0 0 259959467 883862188 0 967049217 0 883862188

例えば、3 番目の選手が優勝するのは次のような場合です。

  • 2 番目の試合で自分が勝ち、3 番目の試合で 5 番目の選手が勝ち、4 番目の試合で 7 番目の選手が勝った場合、\dfrac13 の確率で優勝する。
  • 2 番目の試合で自分が勝ち、3 番目の試合で 6 番目の選手が勝ち、4 番目の試合で 7 番目の選手が勝った場合、\dfrac14 の確率で優勝する。

よって、3 番目の選手が優勝する確率は \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96} です。259959467\times96\equiv7\pmod{998244353} なので、3 番目の選手が優勝する確率は{}\bmod998244353 で 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

Score : 500 points

Problem Statement

A tournament is being held with 2N players. From now on, each player will play exactly one match. In the remaining N matches, the i-th (1\le i\le N) match is played between the (2i-1)-th and 2i-th players.

In each match, one of the two competing players wins and the other loses. Which player wins is determined independently for each match, and each player wins with probability \dfrac12.

Before the last N matches begin, the i-th (1\le i\le2N) player has won A _ i times. After all matches are over, the champion is chosen from among the players with the most wins, uniformly at random and independently of the previous match results.

For each of the first, second, \ldots, 2N-th players, find the probability, modulo 998244353, of that player becoming the champion.

Definition of probability modulo 998244353

It can be proved that the sought probability is always a rational number. Moreover, under the constraints of this problem, it can be proved that when the rational number is expressed as an irreducible fraction \frac{P}{Q}, we have Q {{}\not\equiv{}} 0 \pmod{998244353}. Therefore, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Find this R.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 0\le A _ i\lt2N\ (1\le i\le 2N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the probability of the first player becoming the champion, the probability of the second player becoming the champion, \ldots, the probability of the 2N-th player becoming the champion, in this order, separated by spaces, on a single line.

Sample Input 1

4
1 2
3 4
2 3
1 4

Sample Output 1

0 0 259959467 883862188 0 967049217 0 883862188

For example, the third player becomes the champion in the following cases:

  • If the third player wins in the second match, the fifth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac13.
  • If the third player wins in the second match, the sixth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac14.

Thus, the probability of the third player becoming the champion is \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}. We have 259959467\times96\equiv7\pmod{998244353}, so the probability of the third player becoming the champion in modulo-998244353 expression is 259959467.

The probability of each player becoming the champion is 0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}. Thus, output 0 0 259959467 883862188 0 967049217 0 883862188.

Sample Input 2

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

Sample Output 2

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

It is possible that no one has won yet.

By symmetry, each player becomes the champion with probability \dfrac1{12}.

Sample Input 3

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

Sample Output 3

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