No.3055 Simple Chicken Game
タグ : / 解いたユーザー数 4
作問者 :
suisen
/ テスター :
emthrm
👑 
rin204
問題文
正整数 $n$ と素数 $p$ が与えられます。$n$ 人のプレイヤー $1,2,\ldots,n$ が次のゲームを行います。
ゲーム
各プレイヤー $i\ (1\leq i\leq n)$ のスコア $a_i$ はゲーム開始時点で $a _ i = {\color{red}-i}$ と初期化されています。
ゲームはプレイヤー $1,2,\ldots,n$ の順に $1$ 回ずつ手番が回ることで終了します。プレイヤー $i$ の手番では次の操作を $0$ 回または $1$ 回だけ行います。操作を行うかどうかは、先に終了したプレイヤー $1,2,\ldots,i-1$ の手番の結果を見てから決めることが出来ます。
操作
$1$ 枚のコインを $1$ 回投げる。表が出たら $a _ i \gets a _ i + 10 ^ 9$、裏が出たら $a _ i \gets a _ i - 10 ^ 9$ と更新する。表が出る確率と裏が出る確率は等しく $1/2$ であり、各試行は独立である。
全てのプレイヤーの手番が終了したとき、スコアの 降順 に $1,2\ldots,n$ 位と順位を定めます（つまり、スコアの高いプレイヤーが上位となります）。本問題の制約下では複数のプレイヤーが同一のスコアを持ち得ないことに注意してください。
各プレイヤーが自身の 順位 の期待値を最小化するように行動したときの、各プレイヤーの 順位 の期待値を $\mathrm{mod}\ p$ で求めてください。ただし、コインを投げる場合と投げない場合で自身の順位の期待値が等しい場合は、確率 $1/2$ でコインを投げる選択をし、確率 $1/2$ でコインを投げない選択をする ものとします。なお、この選択も他の試行と独立であるとします。
さらに、各プレイヤーは、他のプレイヤーも順位の期待値を最小化するように行動すること（操作を行っても行わなくても順位の期待値が等しい場合には上述の法則に基づいて確率的に行動を決定することを含む）を知っているものとします。
期待値を $\mathrm{mod}\ p$ で求めてください とは（クリックで展開）
入力
入力は以下の形式で標準入力から与えられます。
$n$ $p$
- 入力は全て整数で与えられる
- $1 \leq n \leq 3000$
- $10 ^ 8 \leq p \leq 10 ^ 9$ かつ $p$ は素数
出力
プレイヤー $i$ の順位の期待値 $\mathrm{mod}\ p$ を $r _ i$ とし、$r _ 1, r _ 2,\ldots, r _ n$ をこの順に空白区切りで $1$ 行に出力して改行してください。
$r _ 1 \ r _ 2\ \cdots\ r _ n$
サンプル
サンプル1
入力
2 998244353
出力
499122178 499122178
入力は $n=2,\ p=998244353$ を表します。
- プレイヤー $1$ がコインを投げる場合: 下記より、プレイヤー $2$ が最適に行動する場合のプレイヤー $1$ の順位の期待値は $\dfrac{1}{2}\cdot 1 + \dfrac{1}{2}\cdot 2 = \dfrac{3}{2}$ です。
- 表が出た場合: プレイヤー $2$ は行動に依らず必ず $2$ 位になります。つまり、プレイヤー $1$ の順位の期待値は $1$ です。
- 裏が出た場合: プレイヤー $2$ はコインを投げないことで必ず $1$ 位を取ることが出来ます。つまり、プレイヤー $1$ の順位の期待値は $2$ です。
- プレイヤー $1$ がコインを投げない場合: 下記より、プレイヤー $2$ はコインを投げる選択が最適です。そして、この場合のプレイヤー $1$ の順位の期待値は $3/2$ です。
- プレイヤー $2$ がコインを投げない場合: プレイヤー $2$ の順位の期待値は $2$ です。
- プレイヤー $2$ がコインを投げる場合: 確率 $1/2$ で $1$ 位、確率 $1/2$ で $2$ 位なので順位の期待値は $3/2$ です。
結局、プレイヤー $1$ はコインを投げる場合も投げない場合も順位の期待値は等しく $3/2$ です。従って、プレイヤー $1$ は確率 $1/2$ でコインを投げ、確率 $1/2$ でコインを投げません。そのいずれのケースにおいても、プレイヤー $2$ の順位の期待値は $3/2$ なので、プレイヤー $2$ の順位の期待値は $\dfrac{1}{2}\cdot \dfrac{3}{2} + \dfrac{1}{2}\cdot \dfrac{3}{2} = \dfrac{3}{2}$ です。
$2\times R\equiv 1\pmod{p}$ となる唯一の $0$ 以上 $p$ 未満の整数は $499122177$ なので、$3/2$ を $\mathrm{mod}\ p$ で表すと $3\times 499122177\equiv 499122178 \pmod{p}$ です。従って、$r _ 1=r _ 2=499122178$ をそれぞれ出力してください。
サンプル2
入力
10 999999937
出力
348579389 348579389 985794010 10223393 281799304 457885719 263916005 144042966 922851511 236328117
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。