問題一覧 > 通常問題

No.1521 Playing Musical Chairs Alone

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

問題文

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

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

  • 1xL を満たす整数 x を任意に選択する。
  • 時計回りに x 個椅子を移動する。すなわち、現在座っている椅子を 椅子 c として、椅子 ((c+x)modN) に移動する。ただし、amodbab で割った余りを指す。

i (0iN1) について、以下の問題に対する答えを出力してください。

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

入力

N K L
  • 入力はすべて整数
  • 1LN100
  • 1K106

出力

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

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

サンプル

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

01112, 01120, 02210, 022214 通りが考えられます。

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

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

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

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

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