問題一覧 > 通常問題

No.1419 Power Moves

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 56
作問者 : 👑 minatominato / テスター : 👑 maspymaspy
11 ProblemId : 5666 / 出題時の順位表
問題文最終更新日: 2021-03-12 23:59:28

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。