問題一覧 > 通常問題

No.1281 Cigarette Distribution

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 133
作問者 : 👑 platinumplatinum / テスター : mfbgjsczmfbgjscz
15 ProblemId : 4376 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-05 23:35:32

問題文

$X$ 個の空の箱と大量のタバコがあり、A君は箱にタバコを入れていきます。

A君は次の操作を $N$ 回行います。


操作:$2$ 本のタバコを好きな箱に入れる。同じ箱に $2$ 本入れてもよく、$2$ つの箱に $1$ 本ずつタバコを入れてもよい。


タバコの入れ方の”良さ”とは、各箱に入っているタバコの本数のすべての積です。

B君は、A君の各操作の後に”良さ”が最小になるように箱を $1$ つ選択し、そこからタバコを $1$ 本取り除いてA君の邪魔をします。

B君は将来のことは考えず、毎回その時の”良さ”が最小になるように行動します。また、B君が選択しうる箱が複数ある場合はその中からランダムに選択します。

タバコの入れ方の最終的な”良さ”を、B君が最後に邪魔をした後の”良さ”とします。

$X=1,2, \dots, M$ について、A君が達成できる最終的な”良さ”の最大値を求めてください。

なお、タバコは十分多くあり、途中で不足することはないものとします。

答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

入力

$N\ M$

・入力は全て整数である。
・$1 \le M \le N \le 2 \times 10^5$

出力

$M$ 行出力してください。
$i$ 行目には、$X=i$ における"良さ"の最大値を $10^9+7$ で割った余りを出力してください。

サンプル

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

箱は $1$ つしかなく、A君が $2$ 本のタバコを入れてB君が $1$ 本取り除くことを $3$ 回繰り返します。
最終的に箱には $3$ 本のタバコが残り、積は $3$ なので"良さ"は $3$ となります。

サンプル2
入力
2 2
出力
2
0

$X=1$ の場合はサンプルケース $1$ の場合と同様に考えられます。
$X=2$ の場合は次のようになります。
・B君が $1$ 回目に邪魔をした後、片方の箱に $1$ 本、もう一方の箱には $0$ 本のタバコがある
・A君の $2$ 回目の操作にかかわらず、B君はどちらかの箱のタバコを $0$ 本にできる
したがって、各箱の本数の積である"良さ"は $0$ になってしまいます。

サンプル3
入力
5 3
出力
5
6
4

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