K个逆序对数组（K Inverse Pairs Array）

题目描述
给定两个整数 n 和 k，你需要计算出包含从 1 到 n 的数字组成的数组的数量，这些数组恰好包含 k 个逆序对。由于答案可能很大，请返回结果对 10⁹ + 7 取模后的值。

逆序对的定义：在一个数组中，如果存在两个索引 i 和 j（i < j）且 arr[i] > arr[j]，则称这是一个逆序对。

示例
输入：n = 3, k = 1
输出：2
解释：
数组 [1,3,2] 和 [2,1,3] 都包含恰好 1 个逆序对。
（[1,3,2] 中逆序对是 (3,2)；[2,1,3] 中逆序对是 (2,1)）

约束条件

• 1 <= n <= 1000
• 0 <= k <= 1000

解题过程

这个问题是经典的动态规划计数问题。关键在于如何逐步构造数组，并跟踪逆序对的数量变化。

第一步：理解问题核心

我们需要计算长度为 n 的排列（由 1 到 n 的数字组成）的数量，这些排列恰好有 k 个逆序对。
直接枚举所有排列（n! 个）不现实，因为 n 最大 1000。
我们需要找到一种递推关系，利用动态规划来计数。

第二步：寻找递推思路

假设我们已经知道如何为 n-1 个数字构建排列，现在要加入数字 n。
数字 n 是当前最大的数字，它放在不同位置会影响逆序对的数量。

举例：n = 4，我们已经有一个长度为 3 的排列，比如 [2,1,3]（它有 1 个逆序对 (2,1)）。
现在插入数字 4 到这个排列的某个位置：

1. 插入到最前面：[4,2,1,3] → 新增逆序对：(4,2)、(4,1)、(4,3)，共新增 3 个逆序对。
2. 插入到第二个位置：[2,4,1,3] → 新增逆序对：(4,1)、(4,3)，共新增 2 个。
3. 插入到第三个位置：[2,1,4,3] → 新增逆序对：(4,3)，新增 1 个。
4. 插入到最后面：[2,1,3,4] → 新增 0 个逆序对。

规律：当把数字 n 插入到长度为 n-1 的排列的第 j 个位置时（位置从 0 开始计数，即前面有 j 个数字），新增的逆序对数量是 (n-1) - j。
因为数字 n 比前面所有数字都大，所以不会与前面的数字形成逆序对。但它会比它后面的 (n-1-j) 个数字大，因此会与它们每一个形成逆序对。

第三步：定义状态

设 dp[n][k] 表示：由 1 到 n 的数字组成的排列中，恰好有 k 个逆序对的排列数量。

第四步：状态转移方程

基于上面的插入思路：
当我们从 dp[n-1][*] 构建 dp[n][*] 时，数字 n 可以插入到 n 个不同位置（0 到 n-1）。
如果我们在长度为 n-1 的排列中有 x 个逆序对，把数字 n 插入到位置 j（从 0 开始），则新排列的逆序对数为：

\[\text{新的逆序对数} = x + (n-1 - j) \]

因为插入位置 j 会新增 (n-1 - j) 个逆序对。

因此，对于固定的 n 和 k，我们可以从 n-1 的某个状态转移过来：

\[dp[n][k] = \sum_{j=0}^{n-1} dp[n-1][k - (n-1 - j)] \]

其中，我们需要确保 k - (n-1 - j) >= 0，即 k - (n-1 - j) ≥ 0，所以 j 必须满足 j ≥ n-1 - k。

换个写法，令 t = n-1 - j，则 t 表示新增的逆序对数，t 从 0 到 n-1。那么：

\[dp[n][k] = \sum_{t=0}^{\min(n-1, k)} dp[n-1][k - t] \]

因为 t 最大为 n-1，且 k - t 不能为负。

举例验证：n=3, k=1
已知 n=2 时：
dp[2][0] = 1（排列 [1,2] 逆序对0）
dp[2][1] = 1（排列 [2,1] 逆序对1）
dp[2][2] = 0

对于 dp[3][1]：

• t=0（新增0个逆序对）：需要 dp[2][1] = 1
• t=1（新增1个逆序对）：需要 dp[2][0] = 1
• t=2（新增2个逆序对）：需要 dp[2][-1] 不存在（忽略）
  所以 dp[3][1] = 1+1 = 2，与示例一致。

第五步：优化递推复杂度

直接按上述递推计算，时间复杂度为 O(n²k)，当 n 和 k 最大 1000 时，运算量可达 10⁹，会超时。
我们需要优化。

观察：

\[dp[n][k] = \sum_{t=0}^{\min(n-1, k)} dp[n-1][k - t] \]

这实际上是一个前缀和的形式。
如果定义前缀和：

\[prefix[n-1][k] = \sum_{i=0}^{k} dp[n-1][i] \]

那么：

\[dp[n][k] = prefix[n-1][k] - prefix[n-1][k - \min(n-1, k) - 1?] \]

更准确地说：

\[dp[n][k] = prefix[n-1][k] - (k-n >= 0 ? prefix[n-1][k-n] : 0) \]

因为当 k >= n 时，t 从 0 到 n-1 对应 dp[n-1][k] 到 dp[n-1][k-(n-1)]，即从 prefix[n-1][k] 减去 prefix[n-1][k-n]（如果 k-n >= 0）。
仔细推导：

我们有：

\[dp[n][k] = \sum_{t=0}^{\min(n-1, k)} dp[n-1][k-t] \]

设 m = min(n-1, k)，则求和范围是 dp[n-1][k-m] 到 dp[n-1][k]。
即：

\[dp[n][k] = \sum_{i=k-m}^{k} dp[n-1][i] \]

由于 m = min(n-1, k)，分两种情况：

1. 当 k < n-1 时，m = k，则求和是 dp[n-1][0] 到 dp[n-1][k]，即 prefix[n-1][k]。
2. 当 k >= n-1 时，m = n-1，则求和是 dp[n-1][k-(n-1)] 到 dp[n-1][k]，即 prefix[n-1][k] - prefix[n-1][k-n]。

因此统一公式：

\[dp[n][k] = prefix[n-1][k] - (k >= n ? prefix[n-1][k-n] : 0) \]

其中 prefix[n-1][x] 是 dp[n-1][0..x] 的累积和。

第六步：动态规划实现步骤

1. 初始化：dp[1][0] = 1（只有一个数字，逆序对为0），dp[1][k] = 0（k>0）。
2. 对于每个 n 从 2 到 N：
   • 先计算前缀和数组 prefix_prev 对应 dp[n-1] 的前缀和。
   • 对于每个 k 从 0 到 K：
     • 使用上述公式计算 dp[n][k]。
3. 结果 = dp[N][K] mod MOD。

边界处理：

• 当 k=0 时，dp[n][0] = 1（只有完全升序排列 [1,2,...,n]）。
• 注意前缀和的下标不要越界（k-n 可能为负）。

第七步：空间优化

由于 dp[n][k] 只依赖于 dp[n-1][*]，我们可以用滚动数组优化空间为一维数组 dp[k] 和前缀和数组。
具体：

• 用 dp_cur[k] 表示当前 n 的 dp 值。
• 用 prefix_prev 表示前一轮 dp 的前缀和。
• 每轮更新后，重新计算前缀和供下一轮使用。

时间复杂度：O(n*k)
空间复杂度：O(k)

第八步：示例演算（n=3, k=1）

初始 n=1:
dp = [1, 0, 0, ...]（索引是 k）

n=2 时：
计算 prefix_prev = [1, 1, 1, ...]（前缀和）
对于 k=0: dp_cur[0] = prefix_prev[0] = 1
对于 k=1: dp_cur[1] = prefix_prev[1] - (1>=2? prefix_prev[-1]:0) = 1 - 0 = 1
对于 k=2: dp_cur[2] = prefix_prev[2] - (2>=2? prefix_prev[0]:0) = 1 - 1 = 0
更新 dp = [1,1,0,...]

n=3 时：
prefix_prev = [1, 2, 2, ...]（上一轮 dp 的前缀和）
k=0: dp_cur[0] = prefix_prev[0] = 1
k=1: dp_cur[1] = prefix_prev[1] - (1>=3? prefix_prev[-2]:0) = 2 - 0 = 2
结果 dp[3][1] = 2，符合示例。

第九步：代码框架（关键部分）

MOD = 10**9 + 7

def kInversePairs(n, k):
    dp = [0] * (k + 1)
    dp[0] = 1  # n=1 的情况
    for i in range(2, n + 1):
        new_dp = [0] * (k + 1)
        prefix = [0] * (k + 2)
        # 计算前缀和
        for j in range(k + 1):
            prefix[j + 1] = (prefix[j] + dp[j]) % MOD
        for j in range(k + 1):
            # dp[i][j] = prefix_prev[j] - prefix_prev[j - i] (if j >= i)
            val = prefix[j + 1]  # 注意前缀和下标偏移1
            if j >= i:
                val = (val - prefix[j - i + 1]) % MOD
            new_dp[j] = val
        dp = new_dp
    return dp[k] % MOD

总结
本题核心在于发现插入最大数时新增逆序对数量的规律，然后通过前缀和优化递推求和，将复杂度降至 O(nk)，从而在给定范围内可解。