No.3174 勝ち残りじゃんけん
タグ : / 解いたユーザー数 32
作問者 :
t98slider
/ テスター :
👑 
binap
じゃんけんのルール (クリックで展開します)
じゃんけんとは3種類の手の出し方グー・チョキ・パーでいわゆる三すくみの関係を構成し、その強弱関係により勝敗を決めるものです。
グー、チョキ、パーには以下の関係があります。
- グーはチョキに強い
- チョキはパーに強い
- パーはグーに強い
問題文
初期状態で勝ち残っている人数を $N$ 人として、以下の操作を勝ち残っている人数が $1$ 人 になるまで繰り返します。
操作
- 現時点で勝ち残っている人数が $R$ 人いるとする。
- $R$ 人でじゃんけんをする。$R$ 人はそれぞれグー、チョキ、パーの手を等確率で出す。($3^{R}$ 通りの場合から等確率に選択される。)
- あいこの場合は同じ $R$ 人で次の操作を行う。
- 勝者が $W$ 人、敗者が $R - W$ 人出た場合は勝者 $W$ 人で次の操作を行う。
入力
$N$
制約
- $2 \leq N \leq 5000$
- $N$ は整数
- $1 \leq i \leq 5000$ の範囲内の整数 $i$ において $2 ^{i} \not\equiv 1 \,(\bmod\,998244353)$ が保証されます。
出力
$i$ 人 ($1 \leq i \leq N$)以下になるまでの操作の回数の期待値を $\bmod\,998244353$ としたものを $x_{i}$ としたとき以下の形式で出力してください。最後に改行してください。
$x_{1}$ $x_{2}$ $\cdots$ $x_{N}$
サンプル
サンプル1
入力
2
出力
499122178 0
初期人数 $2$ 人でじゃんけんを行います。
$2$ 人で開始しているので $2$ 人以下になるまでの操作の回数の期待値は $0$ 回です。
$2$ 人でじゃんけんをするとき、あいこになる確率は $\frac{1}{3}$ です。
どちらかが勝つまでじゃんけんをするときの操作の回数の期待値は
$$
\sum_{i=0}^{\infty} \left(\frac{1}{3}\right)^{i} = \frac{1}{1 - \frac{1}{3}} = \frac{3}{2}
$$
回となります。期待値は ${\displaystyle\frac{3}{2}}$ 回なので ${\displaystyle\frac{3}{2}} \equiv 499122178 (\bmod 998244353) $ となります。
$1$ 人以下になるまでに行う操作の回数の期待値は $499122178$
$2$ 人以下になるまでに行う操作の回数の期待値は $0$
としてそれぞれ出力します。
サンプル2
入力
3
出力
748683267 499122178 0
期待値はそれぞれ ${\displaystyle \left[\frac{9}{4},\,\frac{3}{2},\,0\right] }$ となります。
サンプル3
入力
7
出力
382698679 52634013 385382130 292803016 833787052 213909510 0
期待値はそれぞれ ${\displaystyle \left[\frac{225161}{26040},\,\frac{201851}{26040},\,\frac{61497}{8680},\,\frac{28071}{4340},\,\frac{5211}{868},\frac{81}{14},0 \right]}$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。