No.1419 Power Moves
minato
maspyProblem Statement
$N$ cells are arranged in a circle, numbered $0$ to $N-1$ in clockwise order.
You are currently on cell $0$. You perform the following action $K$ times.
- Choose clockwise or counterclockwise with equal probability (this choice is independent of all previous choices). In the $k$-th action, move $2^{k-1}$ cells in the chosen direction.
For each $n = 0,1,\dots,N-1$, solve the following problem.
Find the probability that you are on cell $n$ after the $K$ actions.
The probability can be expressed as $P/Q$ using coprime integers $P$ , $Q$. Output the integer $R$ between $0$ and $10^9+6$, inclusive, such that $R \times Q \equiv P\pmod {10^9+7}$. (Under the constraints of this problem, such an $R$ always exists and is unique.)
Input
The input is given from standard input in the following format.
$N\ K$
- $3 \le N\le 10^5$
- $1 \le K\le 10^9$
- All input values are integers.
Output
Output $N$ lines. On the $i$-th line, output the answer for $n = i-1$.
Print a newline at the end.
Sample
Sample 1
Input
3 3
Output
250000002 375000003 375000003
In the $1$-st action, you move $1$ cell clockwise or counterclockwise. After that, the probabilities that you are on cells $0 , 1 , 2$ are $0 , \frac{1}{2} , \frac{1}{2} $, respectively.
In the $2$-nd action, you move $2$ cells clockwise or counterclockwise. After that, the probabilities that you are on cells $0 , 1 , 2$ are $\frac{1}{2} , \frac{1}{4} , \frac{1}{4} $, respectively.
In the $3$-rd action, you move $4$ cells clockwise or counterclockwise. After that, the probabilities that you are on cells $0 , 1 , 2$ are $\frac{1}{4} , \frac{3}{8} , \frac{3}{8} $, respectively.
Sample 2
Input
6 7
Output
0 523437504 0 953125007 0 523437504
Sample 3
Input
7 11
Output
408203128 943847663 408203128 943847663 943847663 408203128 943847663
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。