問題一覧 > 通常問題

No.1521 Playing Musical Chairs Alone

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 83
作問者 : aspiaspi / テスター : NatsubiSoganNatsubiSogan nok0nok0 NachiaNachia
1 ProblemId : 5892 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-13 22:28:59

問題文

$N$ 個の椅子が円環状に並んでおり、時計回りに $0$ から $N-1$ までの番号がついています。

aspi 君ははじめ 椅子 $0$ に座っており、これから以下の一連の行動をちょうど $K$ 回繰り返します。

  • $1 \leq x \leq L$ を満たす整数 $x$ を任意に選択する。
  • 時計回りに $x$ 個椅子を移動する。すなわち、現在座っている椅子を 椅子 $c$ として、椅子 $((c+x) \bmod N)$ に移動する。ただし、$a \bmod b$ は $a$ を $b$ で割った余りを指す。

各 $i\ (0 \leq i \leq N-1)$ について、以下の問題に対する答えを出力してください。

  • 移動方法として考えられる $L^K$ 通りのうち、$K$ 回の移動がすべて終了したのち aspi 君が 椅子 $i$ に座っているようなものはいくつでしょうか。ただし、答えは非常に大きくなることがあるので、$10^9+7$(素数)で割った余りを求めてください。

入力

$N\ K\ L$
  • 入力はすべて整数
  • $1\leq L \leq N \leq 100$
  • $1 \leq K \leq 10^{6}$

出力

$N$ 行出力してください。$i+1\ (0 \leq i \leq N-1)$ 行目には、aspi 君が最終的に 椅子 $i$ に座っているような移動方法の数を $10^9+7$ で割った余りを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 2 2
出力
2
1
1

$0 \xrightarrow{1} 1 \xrightarrow{1} 2,\ 0 \xrightarrow{1} 1 \xrightarrow{2} 0,\ 0 \xrightarrow{2} 2 \xrightarrow{1} 0,\ 0 \xrightarrow{2} 2 \xrightarrow{2} 1$ の $4$ 通りが考えられます。

サンプル2
入力
4 1000000 1
出力
1
0
0
0

常に隣に進み続けるしかありません。

サンプル3
入力
10 1000000 5  
出力
980155759
695194657
838549546
695181520
838536409
553575307
838536409
695181520
838549546
695194657

答えを $10^9+7$ で割った余りを出力することを忘れないようにしてください。

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