問題一覧 > 通常問題

No.1866 Unfair Tournament

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : Cyanmond / テスター : shiomusubi496 ytqm3
お気に入りにしたユーザー ProblemId : 7437 / 自分の提出
問題文最終更新日: 2023-06-14 20:49:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 334 (順位表) の他の問題:

Problem Statement

There are $2^N$ players, numbered $1,2,\ldots,2^N$. These players take part in a tournament.

The tournament is held as follows.

  • Generate a permutation $P$ of $2^N$ elements uniformly at random, and line up the players in the order $P_1,P_2,\ldots,P_{2^N}$ from the left.
  • Repeat the following until only one player remains in the line.
    • The $1$-st and $2$-nd players from the left form a pair, the $3$-rd and $4$-th players form a pair, $\ldots$.
    • The two players of each pair play a match, and the loser leaves the line.
  • The player who remains at the end is the winner of the tournament.

Here, when player $a$ and player $b$ satisfying $1 \le a < b \le 2^N$ play a match, player $a$ wins with probability $\frac{A}{B}$. There are no draws.

For each $k = 1,2,\ldots ,2^N$, find the probability that player $k$ wins the tournament, $\bmod 998244353$.


Note on the output (click to expand)
It can be proved that the values to be output in this problem are rational numbers. It can also be proved that, when such a value is written as an irreducible fraction $\frac{y}{x}$, $x$ is not a multiple of $998244353$.
Here, the integer $z \ (0 \le z < 998244353)$ satisfying $xz \equiv y \pmod {998244353}$ is uniquely determined, so output this value as $\frac{y}{x} \bmod 998244353$.

Input

$N$ $A$ $B$
  • $1 \le N \le 18$
  • $1 \le A < B \le 998244352$

Output

Output $2^N$ lines. On the $i$-th line, output the probability that player $i$ wins the tournament.

Sample

Sample 1
Input
1 2 6
Output
332748118
665496236

Only $1$ match is played, so the player who wins that match wins the tournament. Therefore, player $1$ wins the tournament with probability $\frac{1}{3}$, and player $2$ wins the tournament with probability $\frac{2}{3}$.

Note that the input is not necessarily given as an irreducible fraction.

Sample 2
Input
2 1 2
Output
748683265
748683265
748683265
748683265

All players have the same probability of winning the tournament.

Sample 3
Input
3 3 4
Output
577110017
767623169
862879745
914685953
944766977
963149825
974848001
982646785

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