P13969 [VKOSHP 2024] Exchange and Deletion

有一种经典的方法可以从数组中删除一个元素：将要删除的元素与数组的最后一个元素交换，然后删除最后一个元素。 不幸的是，这种方法并不总是能保持数组元素的顺序。你的任务是统计有多少种长度为 $k$ 的删除序列，使得初始为升序排列的数组在经过这些删除操作后仍然保持升序。 给定一个长度为 $n$ 的数组 $a$，初始时 $a_i=i$，即 $a$ 按升序排列。还给定一个长度为 $k$ 的数组 $b$，其中元素是 $1$ 到 $n$ 的两两不同的数。 进行 $k$ 步操作，在第 $j$ 步时，选择一个下标 $i$，满足 $1 \leq i \leq n-j+1$ 且 $a_i = b_j$，然后交换 $a_i$ 和 $a_{n-j+1}$（如果 $i = n-j+1$，则不做任何操作）。接着删除当前数组的最后一个元素（即下标为 $n-j+1$ 的元素）。 如果在 $k$ 步操作后，数组 $[a_1,a_2,\ldots,a_{n-k}]$ 仍然严格递增，则称数组 $[b_1,b_2,\ldots,b_k]$ 是“好”的。 给定 $n$ 和 $k$，请你计算有多少个“好”的数组 $[b_1,b_2,\ldots,b_k]$。答案可能很大，请输出对 $10^9+7$ 取模后的结果。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 接下来的 $t$ 行，每行描述一个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 5 \cdot 10^5$，$0 \leq k \leq n$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示“好”的数组 $b$ 的数量，对 $10^9+7$ 取模。

我们来分析样例中的第四个测试用例，其中 $n=3$，$k=1$。初始时 $a=[1,2,3]$。 我们来看所有可能的 $b$ 数组，经过第一步操作后 $a$ 的变化。 - $b=[1]$。则 $a$ 变化为：$[1,2,3]\to[3,2,1]\to[3,2]$。数组 $[3,2]$ 不是递增的。 - $b=[2]$。则 $a$ 变化为：$[1,2,3]\to[1,3,2]\to[1,3]$。数组 $[1,3]$ 是递增的。 - $b=[3]$。则 $a$ 变化为：$[1,2,3]\to[1,2,3]\to[1,2]$。数组 $[1,2]$ 是递增的。 可以发现有两种“好”的数组 $b=[2]$ 和 $b=[3]$，所以该测试用例的答案是 $2$。 由 ChatGPT 4.1 翻译