No.1521 Playing Musical Chairs Alone
タグ : / 解いたユーザー数 106
作問者 :
aspi
/ テスター :
NatsubiSogan
nok0
👑 
Nachia
Problem Statement
$N$ chairs are arranged in a circle, numbered from $0$ to $N-1$ in clockwise order.
Aspi is initially sitting on chair $0$, and will now repeat the following sequence of actions exactly $K$ times.
- Choose any integer $x$ satisfying $1 \leq x \leq L$.
- Move $x$ chairs clockwise. That is, letting chair $c$ be the chair he is currently sitting on, move to chair $((c+x) \bmod N)$. Here, $a \bmod b$ denotes the remainder when $a$ is divided by $b$.
For each $i\ (0 \leq i \leq N-1)$, output the answer to the following question.
- Among the $L^K$ possible ways of moving, how many result in Aspi sitting on chair $i$ after all $K$ moves are finished? Since the answer can be very large, find it modulo $10^9+7$ (a prime).
Input
$N\ K\ L$
- All inputs are integers.
- $1\leq L \leq N \leq 100$
- $1 \leq K \leq 10^{6}$
Output
Output $N$ lines. On line $i+1\ (0 \leq i \leq N-1)$, output the number of ways of moving such that Aspi ends up sitting on chair $i$, modulo $10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
3 2 2
Output
2 1 1
The $4$ possible ways are $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$.
Sample 2
Input
4 1000000 1
Output
1 0 0 0
The only option is to keep moving to the next chair every time.
Sample 3
Input
10 1000000 5
Output
980155759 695194657 838549546 695181520 838536409 553575307 838536409 695181520 838549546 695194657
Do not forget to output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。