No.1866 Unfair Tournament
タグ : / 解いたユーザー数 20
作問者 :
shiomusubi496
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もしくは右上の雲マークをクリックしてアカウントを作成してください。