← 返回题目列表

Codeforces · 1958/F

F. 狭窄的路径

中文机器翻译题面 查看原题

Monocarp 正在一个由 $$$2$$$ 行和 $$$n$$$ 列组成的矩阵中徘徊。我们将第 $$$i$$$ 行和 $$$j$$$ 列中的单元格表示为 $$$(i, j)$$$。 Monocarp 从单元格 $$$(1, 1)$$$ 开始,想要到达单元格 $$$(2, n)$$$。

在一次移动中,Monocarp 可以向两个方向之一移动:

- 右 - 从单元格 $$$(i, j)$$$ 到单元格 $$$(i, j + 1)$$$;
- 向下 — 从单元格 $$$(i, j)$$$ 到单元格 $$$(i + 1, j)$$$。

Monocarp 无法走出矩阵。

Polycarp想要阻止Monocarp在矩阵中自由徘徊。为此,他想在矩阵中精确选择 $$$k$$$ 不同的单元格并阻止它们。他无法选择单元格 $$$(1, 1)$$$ 和 $$$(2, n)$$$。

对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$i$$$,Polycarp 想知道他可以用多少种方式准确地阻止 $$$k$$$ 个单元格,以便 Monocarp 从 $$$(1, 1)$$$ 到 $$$(2, n)$$$ 具有恰好 $$$i$$$ 不同的路径。如果一条路径中存在 Monocarp 访问的单元格,而另一条路径中不存在,则认为两条路径不同。

由于路数可能相当大,因此输出它对 $$$10^9 + 7$$$ 取模。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 2 \cdot n - 2$$$) - 矩阵中的列数和 Polycarp 想要阻止的单元格数。

输出

输出 $$$n + 1$$$ 整数:对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$i$$$,精确阻止 $$$k$$$ 个单元格的方法数量,以便 Monocarp 从 $$$(1, 1)$$$ 到 $$$(2, n)$$$ 具有恰好 $$$i$$$ 不同的路径。输出所有答案以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

2 2

输出 #1

1 0 0

输入 #2

10 2

输出 #2

45 24 21 18 15 12 9 6 3 0 0

输入 #3

10 5

输出 #3

7812 420 210 90 30 6 0 0 0 0 0

输入#4

22 10

输出#4

467563090 1847560 1016158 534820 267410 125840 55055 22022 7865 2420 605 110 11 0 0 0 0 0 0 0 0 0 0