311268: CF1958F. Narrow Paths
Description
Monocarp is wandering through a matrix consisting of $2$ rows and $n$ columns. Let's denote the cell in the $i$-th row and $j$-th column as $(i, j)$. Monocarp starts at cell $(1, 1)$ and wants to reach cell $(2, n)$.
In one move, Monocarp can move in one of two directions:
- right — from cell $(i, j)$ to cell $(i, j + 1)$;
- down — from cell $(i, j)$ to cell $(i + 1, j)$.
Monocarp can't go outside the matrix.
Polycarp wants to prevent Monocarp from freely wandering through the matrix. To do this, he wants to choose exactly $k$ different cells in the matrix and block them. He cannot choose cells $(1, 1)$ and $(2, n)$.
For each $i$ from $0$ to $n$, Polycarp wants to know how many ways he can block exactly $k$ cells, so that Monocarp has exactly $i$ different paths from $(1, 1)$ to $(2, n)$. Two paths are considered different if there exists a cell that Monocarp visits in one path but not in the other.
As the number of ways can be quite large, output it modulo $10^9 + 7$.
InputThe only line contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $2 \le k \le 2 \cdot n - 2$) — the number of columns in the matrix and the number of cells Polycarp wants to block.
OutputOutput $n + 1$ integers: for each $i$ from $0$ to $n$, the number of ways to block exactly $k$ cells, so that Monocarp has exactly $i$ different paths from $(1, 1)$ to $(2, n)$. Output all answers modulo $10^9 + 7$.
ExamplesInput2 2Output
1 0 0Input
10 2Output
45 24 21 18 15 12 9 6 3 0 0Input
10 5Output
7812 420 210 90 30 6 0 0 0 0 0Input
22 10Output
467563090 1847560 1016158 534820 267410 125840 55055 22022 7865 2420 605 110 11 0 0 0 0 0 0 0 0 0 0
Output
F. 狭窄路径
Monocarp 正在一个由两行 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)。
对于每个 i 从 0 到 n，Polycarp 想要知道他有多少种方式封锁恰好 k 个单元格，使得 Monocarp 从 (1, 1) 到 (2, n) 有恰好 i 条不同的路径。如果存在一个单元格 Monocarp 在一条路径中访问但在另一条路径中不访问，则认为两条路径是不同的。
由于方案的数量可能非常大，请将答案模上 10^9 + 7 后输出。
输入数据格式：
输入只有一行，包含两个整数 n 和 k（2 ≤ n ≤ 2 × 10^5；2 ≤ k ≤ 2 × n - 2）——矩阵中的列数和 Polycarp 想要封锁的单元格数。
输出数据格式：
输出 n + 1 个整数：对于每个 i 从 0 到 n，封锁恰好 k 个单元格，使得 Monocarp 从 (1, 1) 到 (2, n) 有恰好 i 条不同路径的方案数。将所有答案模上 10^9 + 7 后输出。题目大意： F. 狭窄路径 Monocarp 正在一个由两行 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)。 对于每个 i 从 0 到 n，Polycarp 想要知道他有多少种方式封锁恰好 k 个单元格，使得 Monocarp 从 (1, 1) 到 (2, n) 有恰好 i 条不同的路径。如果存在一个单元格 Monocarp 在一条路径中访问但在另一条路径中不访问，则认为两条路径是不同的。 由于方案的数量可能非常大，请将答案模上 10^9 + 7 后输出。 输入数据格式： 输入只有一行，包含两个整数 n 和 k（2 ≤ n ≤ 2 × 10^5；2 ≤ k ≤ 2 × n - 2）——矩阵中的列数和 Polycarp 想要封锁的单元格数。 输出数据格式： 输出 n + 1 个整数：对于每个 i 从 0 到 n，封锁恰好 k 个单元格，使得 Monocarp 从 (1, 1) 到 (2, n) 有恰好 i 条不同路径的方案数。将所有答案模上 10^9 + 7 后输出。