問題一覧 > 通常問題

No.3174 Elimination Rock-Paper-Scissors

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 35
作問者 : t98slider / テスター : 👑 binap
お気に入りにしたユーザー ProblemId : 11980 / 自分の提出
問題文最終更新日: 2025-06-02 05:56:49
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 469 (順位表) の他の問題:
Rules of rock-paper-scissors (click to expand)

Rock-paper-scissors is a game in which the three possible hands, Rock, Scissors, and Paper, form a so-called three-way standoff, and the outcome is decided by which hand beats which.
Rock, Scissors, and Paper have the following relations.

  • Rock beats Scissors
  • Scissors beats Paper
  • Paper beats Rock
If everyone playing shows the same hand, or if there is at least one person showing each of Rock, Scissors, and Paper, the game is a draw.

Problem Statement

Initially, $N$ people remain in the game. The following operation is repeated until exactly $1$ person remains.

Operation

  • Let $R$ be the number of people currently remaining.
  • The $R$ people play rock-paper-scissors. Each of the $R$ people shows Rock, Scissors, or Paper with equal probability. (One of the $3^{R}$ possible cases is chosen with equal probability.)
  • In the case of a draw, the same $R$ people perform the next operation.
  • If there are $W$ winners and $R - W$ losers, the $W$ winners perform the next operation.
For each $i$ ($1 \leq i \leq N$), find the expected number of operations performed until the number of remaining people becomes at most that value, $\bmod\,998244353$. More precisely, when the expected value is expressed as an irreducible fraction $P/Q$, there is a unique integer $R$ satisfying $R \times Q≡P (\bmod\,998244353), 0 \leq R < 998244353$; output that $R$.

Input

$N$

Constraints

  • $2 \leq N \leq 5000$
  • $N$ is an integer
Note
  • For every integer $i$ in the range $1 \leq i \leq 5000$, it is guaranteed that $2 ^{i} \not\equiv 1 \,(\bmod\,998244353)$.

Output

Let $x_{i}$ be the expected number of operations until at most $i$ people ($1 \leq i \leq N$) remain, taken $\bmod\,998244353$. Output in the following format. Print a newline at the end. 

$x_{1}$ $x_{2}$ $\cdots$ $x_{N}$

Sample

Sample 1
Input
2
Output
499122178 0

Rock-paper-scissors is played with an initial count of $2$ people.
Since the game starts with $2$ people, the expected number of operations until at most $2$ people remain is $0$.
When $2$ people play rock-paper-scissors, the probability of a draw is $\frac{1}{3}$.
The expected number of operations when playing until one of them wins is $$ \sum_{i=0}^{\infty} \left(\frac{1}{3}\right)^{i} = \frac{1}{1 - \frac{1}{3}} = \frac{3}{2} $$ . The expected value is ${\displaystyle\frac{3}{2}}$ operations, so we have ${\displaystyle\frac{3}{2}} \equiv 499122178 (\bmod 998244353) $.
The expected number of operations until at most $1$ person remains is $499122178$,
and the expected number of operations until at most $2$ people remain is $0$,
and these are output respectively.

Sample 2
Input
3
Output
748683267 499122178 0

The expected values are ${\displaystyle \left[\frac{9}{4},\,\frac{3}{2},\,0\right] }$, respectively.

Sample 3
Input
7
Output
382698679 52634013 385382130 292803016 833787052 213909510 0

The expected values are ${\displaystyle \left[\frac{225161}{26040},\,\frac{201851}{26040},\,\frac{61497}{8680},\,\frac{28071}{4340},\,\frac{5211}{868},\frac{81}{14},0 \right]}$, respectively.

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