线性动态规划：恰好有K个逆序对的数组数量

字数 7611 2025-12-18 13:56:01

线性动态规划：恰好有K个逆序对的数组数量

问题描述

给定两个整数 n 和 k，我们需要找出所有由 1 到 n 组成的长度为 n 的排列中，恰好包含 k 个逆序对的排列数量。由于答案可能非常大，通常会要求对一个大质数（如 10^9 + 7）取模后返回。

逆序对的定义：在一个排列中，如果存在两个下标 i 和 j（i < j），但排列中的元素满足 a[i] > a[j]，则称 (i, j) 是一个逆序对。

示例：

输入：n = 3, k = 1
输出：2
解释：对于 [1, 2, 3] 的所有排列：
- [1, 2, 3]：逆序对数为 0。
- [1, 3, 2]：存在 (3, 2)，逆序对数为 1。
- [2, 1, 3]：存在 (2, 1)，逆序对数为 1。
- [2, 3, 1]：存在 (2, 1), (3, 1)，逆序对数为 2。
- [3, 1, 2]：存在 (3, 1), (3, 2)，逆序对数为 2。
- [3, 2, 1]：存在 (3, 2), (3, 1), (2, 1)，逆序对数为 3。
  所以恰好有 1 个逆序对的排列有两个：[1, 3, 2] 和 [2, 1, 3]。

这是一个典型的计数类动态规划问题，我们需要设计状态转移，避免直接枚举所有排列（n! 的复杂度不可接受）。

解题思路

我们采用线性动态规划的思想，逐步构建排列，并记录逆序对的数量。

1. 定义状态

设 dp[i][j] 表示：考虑数字 1 到 i 的所有排列（即长度为 i 的排列），恰好包含 j 个逆序对的排列数量。

我们的目标是求 dp[n][k]。

2. 状态转移的思考

如何从 dp[i-1] 推导出 dp[i]？当我们已经知道 1 到 i-1 的排列情况时，现在要把数字 i 插入到一个长度为 i-1 的排列中。

关键观察：

数字 i 是当前所有数字中最大的。
如果我们把 i 插入到一个已有的排列中，它插入的位置会影响新增的逆序对数量。
具体来说，如果 i 被插入到某个位置 p（从 0 开始索引，即从左数第 p+1 个位置），那么：
- 在 i 左侧的 p 个原有元素，由于都小于 i，所以会与 i 形成 p 个新的逆序对（每个原有元素和 i 组成一个逆序对）。
- 在 i 右侧的元素，与 i 的大小关系不会形成新的逆序对（因为它们都比 i 小，且 i 在它们左侧，不满足 i < j 的条件）。
- 此外，原有排列内部的逆序对关系保持不变。

因此，将一个长度为 i-1、有 q 个逆序对的排列，通过插入 i 到位置 p，会得到一个长度为 i、有 q + p 个逆序对的新排列。

3. 状态转移方程

对于 dp[i][j]，它是由所有可能的 dp[i-1][q] 转移而来，其中 q = j - p，且 p 的取值范围是 [0, i-1]（因为插入位置有 i 种可能：最左到最右）。

所以：
dp[i][j] = sum_{p=0}^{min(i-1, j)} dp[i-1][j-p]

解释：

p 是插入位置带来的新增逆序对数。
j-p 是原有排列的逆序对数。
由于 j-p 不能为负数（逆序对数不能小于 0），所以 p ≤ j。
同时 p 最多为 i-1（插入到最右侧）。

因此，p 的上限是 min(i-1, j)。

4. 初始条件

dp[1][0] = 1：只有一个数字 1 的排列，逆序对数为 0。
dp[1][j] = 0（对于 j > 0）：不可能有逆序对。
更通用地，我们可以设 dp[0][0] = 1（空排列视为有 0 个逆序对），但通常从 i=1 开始递推更方便。

5. 直接实现的复杂度

直接按照上述方程实现，需要三层循环：

外层循环 i 从 1 到 n。
中层循环 j 从 0 到 k。
内层循环 p 从 0 到 min(i-1, j)。

时间复杂度为 O(n * k * min(n, k))，在 n 和 k 较大时（比如 n=1000, k=1000）会达到约 10^9 量级，不可接受。

6. 优化状态转移

注意到内层循环是在求和：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-min(i-1, j)]。

这实际上是一个前缀和的形式。我们可以维护一个前缀和数组来优化。

定义 prefix[i-1][j] = sum_{t=0}^{j} dp[i-1][t]。

那么：
dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i]（当 j-i >= 0 时）
dp[i][j] = prefix[i-1][j]（当 j-i < 0 时）

这是因为：
sum_{p=0}^{min(i-1, j)} dp[i-1][j-p] 等价于 sum_{t=j-min(i-1, j)}^{j} dp[i-1][t]。
由于 min(i-1, j) 可能是 i-1（当 j >= i-1）或 j（当 j < i-1）。

当 j >= i-1 时，求和下限是 j-(i-1)，即 j-i+1。所以 dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i]。
当 j < i-1 时，求和下限是 j-j = 0，所以 dp[i][j] = prefix[i-1][j]。

更简洁的写法是：
dp[i][j] = prefix[i-1][j] - (j >= i ? prefix[i-1][j-i] : 0)

这样，我们就可以在 O(1) 时间内计算 dp[i][j]。而 prefix[i-1] 可以在计算完 dp[i-1] 后通过一次遍历得到（O(k) 时间）。

因此总时间复杂度优化为 O(n * k)。

7. 空间优化

由于 dp[i] 只依赖于 dp[i-1]，我们可以使用滚动数组，只保留两行：当前行和上一行。
进一步，我们可以在同一数组上就地更新吗？注意 dp[i][j] 依赖于 dp[i-1][j] 和更小的索引，所以如果从 j=0 到 k 顺序更新，会覆盖掉上一行的值。但如果我们从 j=k 递减到 0 更新呢？也不行，因为 dp[i][j] 需要的是 dp[i-1][j] 和 dp[i-1][j-i]（更小的索引）。如果从大到小更新，那么 dp[i-1][j-i] 可能已经被覆盖成 dp[i][j-i] 了，这会导致错误。

因此，最简单的做法是维护两个数组：dp_prev 和 dp_curr，分别表示上一行和当前行。计算完当前行后，更新前缀和数组，然后交换引用。

8. 边界细节

当 j=0 时，对于任何 i，只有完全升序排列（1,2,...,i）有 0 个逆序对，所以 dp[i][0] = 1。
当 j 很大时（超过 i*(i-1)/2，即最多可能的逆序对数），dp[i][j] = 0。但我们只需计算到 k 为止，所以循环中 j 的范围是 [0, k]，但要注意如果 j > i*(i-1)/2，可以直接设为 0。

在实现中，由于我们使用前缀和优化，j 的范围可以统一为 [0, k]，超出最大可能的部分自然会是 0。

9. 模运算

由于结果可能很大，需要在每次加法和减法后取模，并处理减法可能产生的负数（加 MOD 再取模）。

逐步演算（以 n=3, k=1 为例）

初始化：
设 MOD = 10^9+7。
dp_prev 表示 i=0 的情况？更自然的，我们从 i=1 开始。

i=1：

dp_curr[0] = 1 （排列 [1]）
dp_curr[j] = 0 for j>0。
所以 dp_curr = [1, 0]（假设 k=1，数组长度为 k+1=2）。
更新 prefix_curr：[1, 1]（prefix[j] = sum_{t=0}^{j} dp_curr[t]）。
然后 dp_prev = dp_curr, prefix_prev = prefix_curr。

i=2：
计算 dp_curr[j] for j=0..1。
公式：dp_curr[j] = prefix_prev[j] - (j>=2 ? prefix_prev[j-2] : 0)，但这里 i=2，所以是 j>=2？注意我们当前的 i=2，所以条件是 j >= i 即 j>=2。但 j 最大为 1，所以条件不成立。
因此：

j=0: dp_curr[0] = prefix_prev[0] = 1。解释：将 2 插入到 [1] 的最右侧（位置 p=1），新增逆序对 p=1？等等，这里有问题。让我们手动验证。

手动计算 i=2：
已知 i=1 时，dp[1][0]=1。
现在构造 i=2：

从排列 [1] 开始，插入数字 2。
- 插入到位置 p=0（最左）：得到 [2,1]。新增逆序对 p=0？不对，位置 p 是从 0 开始计数的吗？如果我们把插入位置 p 定义为“在插入后，新元素左边有 p 个元素”，那么：
  插入到最左（p=0）：左边 0 个元素，右边 1 个元素（1）。由于 2>1，且 2 在 1 左边，所以新增逆序对数为 1？不满足我们的公式。
  我们需要统一定义。

重新明确 p 的定义：
设原排列长度为 i-1。将数字 i 插入到该排列中，使得在新排列中，数字 i 的左边有 p 个元素（0 ≤ p ≤ i-1）。那么这 p 个元素都比 i 小，所以每个都会与 i 形成一个逆序对。因此，新增逆序对数为 p。
在上例中，原排列 [1]，插入数字 2。

插入到最左（p=0）：新排列 [2,1]。左边 0 个元素，所以新增逆序对为 0。但实际 [2,1] 中，逆序对是 (2,1)，总数为 1。这是因为原排列 [1] 的逆序对为 0，加上新增的 0，等于 0？显然不对。所以我们的定义有问题。

让我们换个角度：当我们插入一个最大的数字 i 时，它和左边的元素不会形成逆序对（因为左边元素 < i，且索引小于 i 的索引，不满足逆序对定义中的 i<j？）。等等，逆序对定义是 i < j 但 a[i] > a[j]。这里 i 是下标索引。
设原排列为 a[0..i-2]，长度为 i-1。插入数字 i 到位置 p（0≤p≤i-1），新排列为 b。
那么，对于 b 中位于 i 左边的 p 个元素（它们都小于 i），它们的下标都小于 i 的下标，且它们的值都小于 i，所以不构成逆序对。
对于 b 中位于 i 右边的 i-1-p 个元素（它们也都小于 i），它们的下标大于 i 的下标，且值小于 i，因此每一对 (i, 右边元素) 都构成一个逆序对。所以新增逆序对数为 i-1-p。
这才是正确的。

所以，修正后的逻辑：

插入位置 p（左边有 p 个元素） => 新增逆序对数 = (i-1) - p。
原有逆序对数为 q。
新排列逆序对数 = q + (i-1-p)。

因此，状态转移方程应为：
dp[i][j] = sum_{p=0}^{i-1} dp[i-1][j - ((i-1)-p)]，其中要求 j - (i-1-p) >= 0。
设 t = i-1-p，则 t 从 0 到 i-1，p = i-1-t。
所以 dp[i][j] = sum_{t=0}^{i-1} dp[i-1][j - t]，其中 j-t ≥ 0。
即 dp[i][j] = sum_{t=0}^{min(i-1, j)} dp[i-1][j-t]。

这与我们最初的方程一致！所以最初的定义中，我错误地把 p 当成了新增逆序对数，实际上 p 是左边元素个数，新增逆序对数是 i-1-p。但最终方程是相同的。

回到 i=2 的例子：
方程：dp[2][j] = sum_{t=0}^{min(1, j)} dp[1][j-t]。

j=0: min(1,0)=0, 所以求和 t=0..0: dp[1][0] = 1。所以 dp[2][0]=1。
解释：将 2 插入到 [1] 的最右侧（p=1, 左边1个元素，新增逆序对 i-1-p = 0），得到 [1,2]，逆序对为 0。
j=1: min(1,1)=1, 求和 t=0..1: dp[1][1] + dp[1][0] = 0 + 1 = 1。所以 dp[2][1]=1。
解释：t=0 对应 p=1（右边0个元素），即插入最右，新增逆序对 0，需要原排列有 1 个逆序对，但原排列 [1] 只有 0 个，所以 dp[1][1]=0，无贡献。
t=1 对应 p=0（左边0个元素），插入最左，新增逆序对 1，需要原排列有 0 个逆序对，即 [1]，得到 [2,1] 有 1 个逆序对。
所以 dp[2] = [1, 1]。

计算前缀和 prefix_prev for i=1: [1,1]。
现在 i=2, 计算 dp_curr:
公式：dp_curr[j] = prefix_prev[j] - (j>=2 ? prefix_prev[j-2] : 0)？注意这里 min(i-1, j) = min(1, j)，所以求和项数是 min(1,j)+1？不，我们推导的优化公式是：
dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i]（当 j>=i）？注意求和是 sum_{t=0}^{min(i-1, j)} dp[i-1][j-t] = sum_{s=j-min(i-1, j)}^{j} dp[i-1][s]。
设 L = j - min(i-1, j)。
当 j < i-1 时，min(i-1, j)=j，所以 L=0，所以 dp[i][j] = prefix[i-1][j]。
当 j >= i-1 时，min(i-1, j)=i-1，所以 L = j - (i-1) = j-i+1，所以 dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i]。
注意这里是 j-i，不是 j-i+1？因为前缀和 prefix[x] 包含 s=0..x，我们要减去的是 prefix[L-1] 即 prefix[j-i]。验证：
对于 j>=i-1，dp[i][j] = sum_{s=j-i+1}^{j} dp[i-1][s] = prefix[i-1][j] - prefix[i-1][j-i]。
正确。

所以对于 i=2:

j=0: j < i-1 (0<1)，所以 dp[2][0] = prefix[1][0] = 1。
j=1: j >= i-1 (1>=1)，所以 dp[2][1] = prefix[1][1] - prefix[1][1-2]？j-i = 1-2 = -1，prefix[-1] 视为 0。
所以 dp[2][1] = 1 - 0 = 1。
匹配。

i=3：
我们有 dp_prev 为 i=2 的结果：[1,1] (对应 j=0,1)。prefix_prev = [1,2]。
现在计算 i=3, k=1（只计算到 j=1）。
公式：

j=0: j < i-1 (0<2)，所以 dp[3][0] = prefix_prev[0] = 1。
j=1: j >= i-1? 1>=2? false。所以 j < i-1，dp[3][1] = prefix_prev[1] = 2。
所以 dp[3][1] = 2。这就是答案。

手动验证 n=3,k=1 有两个排列，正确。

最终算法步骤

初始化 dp_prev 数组长度为 k+1，全部为 0。dp_prev[0] = 1（对应 i=0 的情况？或者直接从 i=1 开始）。
更直接：令 dp_curr 初始为 i=1 的结果：dp_curr[0]=1，其余为 0。
然后计算 prefix_curr。
对于 i 从 2 到 n：
- 创建新的数组 dp_new 长度 k+1，初始全 0。
- 对于 j 从 0 到 k：
  - 如果 j < i-1: dp_new[j] = prefix_curr[j]
  - 否则: dp_new[j] = (prefix_curr[j] - prefix_curr[j-i] + MOD) % MOD
- 计算 prefix_new 为 dp_new 的前缀和（取模）。
- 将 dp_curr 和 prefix_curr 更新为 dp_new 和 prefix_new。
返回 dp_curr[k]。

注意：在第一步，我们可以直接从 i=1 开始循环，但为了统一，可以在循环外初始化 i=1 的情况，然后循环 i=2..n。

复杂度分析

时间复杂度：O(n * k)，因为对于每个 i，我们计算 dp_new 和 prefix_new 各需要 O(k) 时间。
空间复杂度：O(k)，只存储两个长度为 k+1 的数组。

边界情况处理

如果 k > n*(n-1)/2，答案直接为 0，因为逆序对最多有 n*(n-1)/2 个。
当 k=0 时，答案总是 1（升序排列）。
注意取模运算，减法后加 MOD 再取模，避免负数。

总结

这道题通过动态规划，定义了状态 dp[i][j]，利用插入最大数的思想推导出状态转移方程。通过前缀和优化，将内层求和从 O(min(i, k)) 降到 O(1)，最终在 O(n*k) 时间内解决问题。空间上使用滚动数组优化到 O(k)。理解的关键在于掌握插入新增逆序对的计算和前缀和优化技巧。

线性动态规划：恰好有K个逆序对的数组数量问题描述给定两个整数 n 和 k ，我们需要找出所有由 1 到 n 组成的长度为 n 的排列中，恰好包含 k 个逆序对的排列数量。由于答案可能非常大，通常会要求对一个大质数（如 10^9 + 7）取模后返回。逆序对的定义：在一个排列中，如果存在两个下标 i 和 j （ i < j ），但排列中的元素满足 a[i] > a[j] ，则称 (i, j) 是一个逆序对。示例：输入：n = 3, k = 1 输出：2 解释：对于 [ 1, 2, 3 ] 的所有排列： [ 1, 2, 3 ]：逆序对数为 0。 [ 1, 3, 2 ]：存在 (3, 2)，逆序对数为 1。 [ 2, 1, 3 ]：存在 (2, 1)，逆序对数为 1。 [ 2, 3, 1 ]：存在 (2, 1), (3, 1)，逆序对数为 2。 [ 3, 1, 2 ]：存在 (3, 1), (3, 2)，逆序对数为 2。 [ 3, 2, 1 ]：存在 (3, 2), (3, 1), (2, 1)，逆序对数为 3。所以恰好有 1 个逆序对的排列有两个：[ 1, 3, 2] 和 [ 2, 1, 3 ]。这是一个典型的计数类动态规划问题，我们需要设计状态转移，避免直接枚举所有排列（n ! 的复杂度不可接受）。解题思路我们采用线性动态规划的思想，逐步构建排列，并记录逆序对的数量。 1. 定义状态设 dp[i][j] 表示：考虑数字 1 到 i 的所有排列（即长度为 i 的排列），恰好包含 j 个逆序对的排列数量。我们的目标是求 dp[n][k] 。 2. 状态转移的思考如何从 dp[i-1] 推导出 dp[i] ？当我们已经知道 1 到 i-1 的排列情况时，现在要把数字 i 插入到一个长度为 i-1 的排列中。关键观察：数字 i 是当前所有数字中最大的。如果我们把 i 插入到一个已有的排列中，它插入的位置会影响新增的逆序对数量。具体来说，如果 i 被插入到某个位置 p （从 0 开始索引，即从左数第 p+1 个位置），那么：在 i 左侧的 p 个原有元素，由于都小于 i ，所以会与 i 形成 p 个新的逆序对（每个原有元素和 i 组成一个逆序对）。在 i 右侧的元素，与 i 的大小关系不会形成新的逆序对（因为它们都比 i 小，且 i 在它们左侧，不满足 i < j 的条件）。此外，原有排列内部的逆序对关系保持不变。因此，将一个长度为 i-1 、有 q 个逆序对的排列，通过插入 i 到位置 p ，会得到一个长度为 i 、有 q + p 个逆序对的新排列。 3. 状态转移方程对于 dp[i][j] ，它是由所有可能的 dp[i-1][q] 转移而来，其中 q = j - p ，且 p 的取值范围是 [0, i-1] （因为插入位置有 i 种可能：最左到最右）。所以： dp[i][j] = sum_{p=0}^{min(i-1, j)} dp[i-1][j-p] 解释： p 是插入位置带来的新增逆序对数。 j-p 是原有排列的逆序对数。由于 j-p 不能为负数（逆序对数不能小于 0），所以 p ≤ j 。同时 p 最多为 i-1 （插入到最右侧）。因此， p 的上限是 min(i-1, j) 。 4. 初始条件 dp[1][0] = 1 ：只有一个数字 1 的排列，逆序对数为 0。 dp[1][j] = 0 （对于 j > 0）：不可能有逆序对。更通用地，我们可以设 dp[0][0] = 1 （空排列视为有 0 个逆序对），但通常从 i=1 开始递推更方便。 5. 直接实现的复杂度直接按照上述方程实现，需要三层循环：外层循环 i 从 1 到 n。中层循环 j 从 0 到 k。内层循环 p 从 0 到 min(i-1, j) 。时间复杂度为 O(n * k * min(n, k))，在 n 和 k 较大时（比如 n=1000, k=1000）会达到约 10^9 量级，不可接受。 6. 优化状态转移注意到内层循环是在求和： dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-min(i-1, j)] 。这实际上是一个前缀和的形式。我们可以维护一个前缀和数组来优化。定义 prefix[i-1][j] = sum_{t=0}^{j} dp[i-1][t] 。那么： dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i] （当 j-i >= 0 时） dp[i][j] = prefix[i-1][j] （当 j-i < 0 时）这是因为： sum_{p=0}^{min(i-1, j)} dp[i-1][j-p] 等价于 sum_{t=j-min(i-1, j)}^{j} dp[i-1][t] 。由于 min(i-1, j) 可能是 i-1 （当 j >= i-1 ）或 j （当 j < i-1 ）。当 j >= i-1 时，求和下限是 j-(i-1) ，即 j-i+1 。所以 dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i] 。当 j < i-1 时，求和下限是 j-j = 0 ，所以 dp[i][j] = prefix[i-1][j] 。更简洁的写法是： dp[i][j] = prefix[i-1][j] - (j >= i ? prefix[i-1][j-i] : 0) 这样，我们就可以在 O(1) 时间内计算 dp[i][j] 。而 prefix[i-1] 可以在计算完 dp[i-1] 后通过一次遍历得到（O(k) 时间）。因此总时间复杂度优化为 O(n * k)。 7. 空间优化由于 dp[i] 只依赖于 dp[i-1] ，我们可以使用滚动数组，只保留两行：当前行和上一行。进一步，我们可以在同一数组上就地更新吗？注意 dp[i][j] 依赖于 dp[i-1][j] 和更小的索引，所以如果从 j=0 到 k 顺序更新，会覆盖掉上一行的值。但如果我们从 j=k 递减到 0 更新呢？也不行，因为 dp[i][j] 需要的是 dp[i-1][j] 和 dp[i-1][j-i] （更小的索引）。如果从大到小更新，那么 dp[i-1][j-i] 可能已经被覆盖成 dp[i][j-i] 了，这会导致错误。因此，最简单的做法是维护两个数组： dp_prev 和 dp_curr ，分别表示上一行和当前行。计算完当前行后，更新前缀和数组，然后交换引用。 8. 边界细节当 j=0 时，对于任何 i ，只有完全升序排列（1,2,...,i）有 0 个逆序对，所以 dp[i][0] = 1 。当 j 很大时（超过 i*(i-1)/2 ，即最多可能的逆序对数）， dp[i][j] = 0 。但我们只需计算到 k 为止，所以循环中 j 的范围是 [0, k] ，但要注意如果 j > i*(i-1)/2 ，可以直接设为 0。在实现中，由于我们使用前缀和优化， j 的范围可以统一为 [0, k] ，超出最大可能的部分自然会是 0。 9. 模运算由于结果可能很大，需要在每次加法和减法后取模，并处理减法可能产生的负数（加 MOD 再取模）。逐步演算（以 n=3, k=1 为例）初始化：设 MOD = 10^9+7。 dp_prev 表示 i=0 的情况？更自然的，我们从 i=1 开始。 i=1 ： dp_curr[0] = 1 （排列 [ 1 ]） dp_curr[j] = 0 for j>0。所以 dp_curr = [1, 0] （假设 k=1，数组长度为 k+1=2）。更新 prefix_curr ： [1, 1] （prefix[ j] = sum_ {t=0}^{j} dp_ curr[ t ]）。然后 dp_prev = dp_curr , prefix_prev = prefix_curr 。 i=2 ：计算 dp_curr[j] for j=0..1。公式： dp_curr[j] = prefix_prev[j] - (j>=2 ? prefix_prev[j-2] : 0) ，但这里 i=2，所以是 j>=2 ？注意我们当前的 i=2，所以条件是 j >= i 即 j>=2 。但 j 最大为 1，所以条件不成立。因此： j=0: dp_curr[0] = prefix_prev[0] = 1 。解释：将 2 插入到 [ 1 ] 的最右侧（位置 p=1），新增逆序对 p=1？等等，这里有问题。让我们手动验证。手动计算 i=2：已知 i=1 时， dp[1][0]=1 。现在构造 i=2：从排列 [ 1 ] 开始，插入数字 2。插入到位置 p=0（最左）：得到 [ 2,1 ]。新增逆序对 p=0？不对，位置 p 是从 0 开始计数的吗？如果我们把插入位置 p 定义为“在插入后，新元素左边有 p 个元素”，那么：插入到最左（p=0）：左边 0 个元素，右边 1 个元素（1）。由于 2>1，且 2 在 1 左边，所以新增逆序对数为 1？不满足我们的公式。我们需要统一定义。重新明确 p 的定义：设原排列长度为 i-1。将数字 i 插入到该排列中，使得在新排列中，数字 i 的左边有 p 个元素（0 ≤ p ≤ i-1）。那么这 p 个元素都比 i 小，所以每个都会与 i 形成一个逆序对。因此，新增逆序对数为 p 。在上例中，原排列 [ 1 ]，插入数字 2。插入到最左（p=0）：新排列 [ 2,1]。左边 0 个元素，所以新增逆序对为 0。但实际 [ 2,1] 中，逆序对是 (2,1)，总数为 1。这是因为原排列 [ 1 ] 的逆序对为 0，加上新增的 0，等于 0？显然不对。所以我们的定义有问题。让我们换个角度：当我们插入一个最大的数字 i 时，它和左边的元素不会形成逆序对（因为左边元素 < i，且索引小于 i 的索引，不满足逆序对定义中的 i<j？）。等等，逆序对定义是 i < j 但 a[ i] > a[ j ]。这里 i 是下标索引。设原排列为 a[ 0..i-2 ]，长度为 i-1。插入数字 i 到位置 p（0≤p≤i-1），新排列为 b。那么，对于 b 中位于 i 左边的 p 个元素（它们都小于 i），它们的下标都小于 i 的下标，且它们的值都小于 i，所以不构成逆序对。对于 b 中位于 i 右边的 i-1-p 个元素（它们也都小于 i），它们的下标大于 i 的下标，且值小于 i，因此每一对 (i, 右边元素) 都构成一个逆序对。所以新增逆序对数为 i-1-p 。这才是正确的。所以，修正后的逻辑：插入位置 p（左边有 p 个元素） => 新增逆序对数 = (i-1) - p。原有逆序对数为 q。新排列逆序对数 = q + (i-1-p)。因此，状态转移方程应为： dp[i][j] = sum_{p=0}^{i-1} dp[i-1][j - ((i-1)-p)] ，其中要求 j - (i-1-p) >= 0 。设 t = i-1-p，则 t 从 0 到 i-1，p = i-1-t。所以 dp[i][j] = sum_{t=0}^{i-1} dp[i-1][j - t] ，其中 j-t ≥ 0。即 dp[i][j] = sum_{t=0}^{min(i-1, j)} dp[i-1][j-t] 。这与我们最初的方程一致！所以最初的定义中，我错误地把 p 当成了新增逆序对数，实际上 p 是左边元素个数，新增逆序对数是 i-1-p。但最终方程是相同的。回到 i=2 的例子：方程： dp[2][j] = sum_{t=0}^{min(1, j)} dp[1][j-t] 。 j=0: min(1,0)=0, 所以求和 t=0..0: dp[ 1][ 0] = 1。所以 dp[ 2][ 0 ]=1。解释：将 2 插入到 [ 1] 的最右侧（p=1, 左边1个元素，新增逆序对 i-1-p = 0），得到 [ 1,2 ]，逆序对为 0。 j=1: min(1,1)=1, 求和 t=0..1: dp[ 1][ 1] + dp[ 1][ 0] = 0 + 1 = 1。所以 dp[ 2][ 1 ]=1。解释：t=0 对应 p=1（右边0个元素），即插入最右，新增逆序对 0，需要原排列有 1 个逆序对，但原排列 [ 1] 只有 0 个，所以 dp[ 1][ 1 ]=0，无贡献。 t=1 对应 p=0（左边0个元素），插入最左，新增逆序对 1，需要原排列有 0 个逆序对，即 [ 1]，得到 [ 2,1 ] 有 1 个逆序对。所以 dp[ 2] = [ 1, 1 ]。计算前缀和 prefix_ prev for i=1: [ 1,1 ]。现在 i=2, 计算 dp_ curr: 公式： dp_curr[j] = prefix_prev[j] - (j>=2 ? prefix_prev[j-2] : 0) ？注意这里 min(i-1, j) = min(1, j)，所以求和项数是 min(1,j)+1？不，我们推导的优化公式是： dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i] （当 j>=i）？注意求和是 sum_ {t=0}^{min(i-1, j)} dp[ i-1][ j-t] = sum_ {s=j-min(i-1, j)}^{j} dp[ i-1][ s ]。设 L = j - min(i-1, j)。当 j < i-1 时，min(i-1, j)=j，所以 L=0，所以 dp[ i][ j] = prefix[ i-1][ j ]。当 j >= i-1 时，min(i-1, j)=i-1，所以 L = j - (i-1) = j-i+1，所以 dp[ i][ j] = prefix[ i-1][ j] - prefix[ i-1][ j-i ]。注意这里是 j-i ，不是 j-i+1 ？因为前缀和 prefix[ x] 包含 s=0..x，我们要减去的是 prefix[ L-1] 即 prefix[ j-i ]。验证：对于 j>=i-1，dp[ i][ j] = sum_ {s=j-i+1}^{j} dp[ i-1][ s] = prefix[ i-1][ j] - prefix[ i-1][ j-i ]。正确。所以对于 i=2: j=0: j < i-1 (0<1)，所以 dp[ 2][ 0] = prefix[ 1][ 0 ] = 1。 j=1: j >= i-1 (1>=1)，所以 dp[ 2][ 1] = prefix[ 1][ 1] - prefix[ 1][ 1-2]？j-i = 1-2 = -1，prefix[ -1 ] 视为 0。所以 dp[ 2][ 1 ] = 1 - 0 = 1。匹配。 i=3 ：我们有 dp_ prev 为 i=2 的结果：[ 1,1] (对应 j=0,1)。prefix_ prev = [ 1,2 ]。现在计算 i=3, k=1（只计算到 j=1）。公式： j=0: j < i-1 (0<2)，所以 dp[ 3][ 0] = prefix_ prev[ 0 ] = 1。 j=1: j >= i-1? 1>=2? false。所以 j < i-1，dp[ 3][ 1] = prefix_ prev[ 1 ] = 2。所以 dp[ 3][ 1 ] = 2。这就是答案。手动验证 n=3,k=1 有两个排列，正确。最终算法步骤初始化 dp_prev 数组长度为 k+1，全部为 0。 dp_prev[0] = 1 （对应 i=0 的情况？或者直接从 i=1 开始）。更直接：令 dp_curr 初始为 i=1 的结果： dp_curr[0]=1 ，其余为 0。然后计算 prefix_curr 。对于 i 从 2 到 n：创建新的数组 dp_new 长度 k+1，初始全 0。对于 j 从 0 到 k：如果 j < i-1: dp_new[j] = prefix_curr[j] 否则: dp_new[j] = (prefix_curr[j] - prefix_curr[j-i] + MOD) % MOD 计算 prefix_new 为 dp_new 的前缀和（取模）。将 dp_curr 和 prefix_curr 更新为 dp_new 和 prefix_new 。返回 dp_curr[k] 。注意：在第一步，我们可以直接从 i=1 开始循环，但为了统一，可以在循环外初始化 i=1 的情况，然后循环 i=2..n。复杂度分析时间复杂度：O(n * k)，因为对于每个 i，我们计算 dp_ new 和 prefix_ new 各需要 O(k) 时间。空间复杂度：O(k)，只存储两个长度为 k+1 的数组。边界情况处理如果 k > n* (n-1)/2，答案直接为 0，因为逆序对最多有 n* (n-1)/2 个。当 k=0 时，答案总是 1（升序排列）。注意取模运算，减法后加 MOD 再取模，避免负数。总结这道题通过动态规划，定义了状态 dp[i][j] ，利用插入最大数的思想推导出状态转移方程。通过前缀和优化，将内层求和从 O(min(i, k)) 降到 O(1)，最终在 O(n* k) 时间内解决问题。空间上使用滚动数组优化到 O(k)。理解的关键在于掌握插入新增逆序对的计算和前缀和优化技巧。