Blue and Red Balls

题目描述

有 $K$ 个蓝球和 $N-K$ 个红球。同色的球不可区分。Snuke 和 Takahashi 在这些球上进行游戏。 首先，Snuke 将这 $N$ 个球从左到右排列成一行。 然后，Takahashi 只会收集 $K$ 个蓝球。在一次操作中，他可以收集任意多个连续的蓝球。他会以最少的操作次数收集完所有蓝球。 问：Snuke 将 $N$ 个球排列成一行，使得 Takahashi 恰好需要 $i$ 次操作来收集完所有蓝球的排列方式有多少种？对于每个 $1 \leq i \leq K$，将该数量对 $10^9+7$ 取模后输出。

输入格式

输入由标准输入给出，格式如下： $N$ $K$

输出格式

输出 $K$ 行。第 $i$ 行（$1 \leq i \leq K$）应当包含将 $N$ 个球排列成使得 Takahashi 恰好需要 $i$ 次操作来收集完所有蓝球的排列数，对 $10^9+7$ 取模后的值。

5 3

3
6
1

2000 3

1998
3990006
327341989

提示

$1 \leq K \leq N \leq 2000$有三种方法能使 Takahashi 恰好需要一次操作： (B, B, B, R, R)、(R, B, B, B, R) 和 (R, R, B, B, B)。(R 和 B 分别表示红和蓝) 有六种方法能使 Takahashi 恰好需要两次操作： (B, B, R, B, R)、(B, B, R, R, B)、(R, B, B, R, B)、(R, B, R, B, B)、(B, R, B, B, R) 和 (B, R, R, B, B)。 有一种方法能使 Takahashi 恰好需要三次操作： (B, R, B, R, B)。
注意要对 $10^9+7$ 取模后输出排列数。

标签: AtCoder|abc132D

来源

AtCoder|abc132D