No.1419 Power Moves
タグ : / 解いたユーザー数 72
作問者 :
minato
/ テスター :
maspy
問題文
$N$ 個のマスが円環状に並んでおり、時計回りに順に $0$ ～ $N-1$ までの番号が付けられています。
あなたは今マス $0$ の上にいます。あなたは次の行動を $K$ 回行います。
- 時計回りか反時計回りかを等確率で選ぶ（この選択は今までの選択とは独立である）。 $k$ 回目の行動では、選んだ方向に $2^{k-1}$ マスだけ進む。
各 $n = 0,1,\dots,N-1$ について、以下の問題の答えを求めてください。
$K$ 回の行動のあと、あなたがマス $n$ の上にいる確率を求めよ。
求める確率は互いに素な整数 $P$ , $Q$ を用いて、 $P/Q$ と表せます。 $R \times Q \equiv P\pmod {10^9+7}$ となる $0$ 以上 $10^9+6$ 以下の整数 $R$ を出力してください。（この問題の制約下で、このような $R$ は必ず一意に存在します。）
入力
入力は以下の形式で標準入力から与えられる。
$N\ K$
- $3 \le N\le 10^5$
- $1 \le K\le 10^9$
- 入力される数は全て整数。
出力
$N$ 行出力せよ。 $i$ 行目には $n = i-1$ のときの答えを出力せよ。
最後に改行を出力すること。
サンプル
サンプル1
入力
3 3
出力
250000002 375000003 375000003
$1$ 回目の行動ではあなたは時計回りまたは反時計回りに $1$ マスだけ進みます。その後、あなたがマス $0 , 1 , 2$ の上にいる確率は、それぞれ $0 , \frac{1}{2} , \frac{1}{2} $ となります。
$2$ 回目の行動ではあなたは時計回りまたは反時計回りに $2$ マスだけ進みます。その後、あなたがマス $0 , 1 , 2$ の上にいる確率は、それぞれ $\frac{1}{2} , \frac{1}{4} , \frac{1}{4} $ となります。
$3$ 回目の行動ではあなたは時計回りまたは反時計回りに $4$ マスだけ進みます。その後、あなたがマス $0 , 1 , 2$ の上にいる確率は、それぞれ $\frac{1}{4} , \frac{3}{8} , \frac{3}{8} $ となります。
サンプル2
入力
6 7
出力
0 523437504 0 953125007 0 523437504
サンプル3
入力
7 11
出力
408203128 943847663 408203128 943847663 943847663 408203128 943847663
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。