No.1281 Cigarette Distribution
Problem Statement
There are $X$ empty boxes and a large number of cigarettes, and A puts cigarettes into the boxes.
A performs the following operation $N$ times.
Operation: Put $2$ cigarettes into boxes of his choice. He may put $2$ cigarettes into the same box, or he may put $1$ cigarette each into $2$ boxes.
The ”goodness” of a placement of cigarettes is the product of the numbers of cigarettes in all the boxes.
After each of A's operations, B interferes with A by choosing $1$ box so that the ”goodness” is minimized and removing $1$ cigarette from it.
B does not think about the future and always acts so that the ”goodness” at that moment is minimized. If there are multiple boxes B could choose, he chooses one of them at random.
The final ”goodness” of the placement is defined as the ”goodness” after B's last interference.
For each of $X=1,2, \dots, M$, find the maximum final ”goodness” that A can achieve.
Note that there are sufficiently many cigarettes, and they never run out along the way.
Since the answer can be very large, find it modulo $10^9+7$.
Input
$N\ M$
・All inputs are integers.
・$1 \le M \le N \le 2 \times 10^5$
Output
Output $M$ lines.
On the $i$-th line, output the maximum "goodness" for $X=i$, modulo $10^9+7$.
Sample
Sample 1
Input
3 1
Output
3
There is only $1$ box, and A putting in $2$ cigarettes followed by B removing $1$ cigarette is repeated $3$ times.
In the end, $3$ cigarettes remain in the box and the product is $3$, so the "goodness" is $3$.
Sample 2
Input
2 2
Output
2 0
The case $X=1$ can be considered in the same way as Sample Case $1$.
The case $X=2$ goes as follows.
・After B interferes for the $1$st time, one box contains $1$ cigarette and the other box contains $0$ cigarettes.
・Regardless of A's $2$nd operation, B can make the number of cigarettes in one of the boxes $0$.
Therefore, the "goodness", which is the product of the numbers of cigarettes in the boxes, ends up being $0$.
Sample 3
Input
5 3
Output
5 6 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
platinum
leafirby