問題一覧 > 通常問題

No.1866 Unfair Tournament

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : CyanmondCyanmond / テスター : shiomusubi496shiomusubi496 ytqm3ytqm3
2 ProblemId : 7437 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。