No.1521 Playing Musical Chairs Alone
タグ : / 解いたユーザー数 103
作問者 :
aspi
/ テスター :
NatsubiSogan
nok0
👑 
Nachia
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。