No.1866 Unfair Tournament
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 :
Cyanmond
/ テスター :
shiomusubi496
ytqm3
タグ : / 解いたユーザー数 18
作問者 :
Cyanmond
/ テスター :
shiomusubi496
ytqm3
問題文最終更新日: 2023-06-14 20:49:47
問題文
$2^N$ 人の選手がおり、それぞれ $1,2,\ldots,2^N$ と番号がついています。これらの選手でトーナメントをします。
トーナメントは以下のようにして行われます。
- $2^N$ 要素の順列 $P$ を一様ランダムに生成し、選手を左から $P_1,P_2,\ldots,P_{2^N}$ の順になるように並ばせる。
- 並んでいる選手がただ一人になるまで、以下を繰り返す。
- 左から $1$ 番目と $2$ 番目、 $3$ 番目と $4$ 番目、 $\ldots$ の選手が組になる。
- 組になった選手同士で試合をし、負けた人は列を抜ける。
- 最後まで残った選手を、優勝とする。
ここで、 $1 \le a < b \le 2^N$ を満たす選手 $a$ と選手 $b$ が試合をするとき、選手 $a$ が勝つ確率は $\frac{A}{B}$ です。引き分けになることはありません。
$k = 1,2,\ldots ,2^N$ について、選手 $k$ が優勝する確率を $\bmod 998244353$ で求めてください。
出力についての注記 (クリックすると展開されます)
この問題において出力する値は有理数であることが証明できます。また、既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ の倍数でないことも証明できます。ここで、 $xz \equiv y \pmod {998244353}$ を満たす整数 $z \ (0 \le z < 998244353)$ は一意に定まるので、この値を $\frac{y}{x} \bmod 998244353$ として出力してください。
入力
$N$ $A$ $B$
- $1 \le N \le 18$
- $1 \le A < B \le 998244352$
出力
$2^N$ 行出力してください。 $i$ 行目には、選手 $i$ が優勝する確率を出力してください。
サンプル
サンプル1
入力
1 2 6
出力
332748118 665496236
試合は $1$ 回しか行われないため、その試合に勝った選手が優勝となります。よって、選手 $1$ が優勝する確率は $\frac{1}{3}$ 、選手 $2$ が優勝する確率は $\frac{2}{3}$ です。
入力が既約分数とは限らないことに気を付けてください。
サンプル2
入力
2 1 2
出力
748683265 748683265 748683265 748683265
すべての選手の優勝する確率は等しいです。
サンプル3
入力
3 3 4
出力
577110017 767623169 862879745 914685953 944766977 963149825 974848001 982646785
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。