問題一覧 > 通常問題

No.1419 Power Moves

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : minatominato / テスター : maspymaspy
14 ProblemId : 5666 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-12 23:59:28

問題文

N 個のマスが円環状に並んでおり、時計回りに順に 0N1 までの番号が付けられています。

あなたは今マス 0 の上にいます。あなたは次の行動を K 回行います。

  • 時計回りか反時計回りかを等確率で選ぶ(この選択は今までの選択とは独立である)。 k 回目の行動では、選んだ方向に 2k1 マスだけ進む。

n=0,1,,N1 について、以下の問題の答えを求めてください。

K 回の行動のあと、あなたがマス n の上にいる確率を求めよ。

求める確率は互いに素な整数 P , Q を用いて、 P/Q と表せます。 R×QP(mod109+7) となる 0 以上 109+6 以下の整数 R を出力してください。(この問題の制約下で、このような R は必ず一意に存在します。)

入力

入力は以下の形式で標準入力から与えられる。

N K

  • 3N105
  • 1K109
  • 入力される数は全て整数。

出力

N 行出力せよ。 i 行目には n=i1 のときの答えを出力せよ。

最後に改行を出力すること。

サンプル

サンプル1
入力
3 3
出力
250000002
375000003
375000003

1 回目の行動ではあなたは時計回りまたは反時計回りに 1 マスだけ進みます。その後、あなたがマス 0,1,2 の上にいる確率は、それぞれ 0,12,12 となります。

2 回目の行動ではあなたは時計回りまたは反時計回りに 2 マスだけ進みます。その後、あなたがマス 0,1,2 の上にいる確率は、それぞれ 12,14,14 となります。

3 回目の行動ではあなたは時計回りまたは反時計回りに 4 マスだけ進みます。その後、あなたがマス 0,1,2 の上にいる確率は、それぞれ 14,38,38 となります。

サンプル2
入力
6 7
出力
0
523437504
0
953125007
0
523437504

サンプル3
入力
7 11
出力
408203128
943847663
408203128
943847663
943847663
408203128
943847663

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