K个逆序对数组（进阶版：计算恰好具有K个逆序对的n个数的排列数目，并考虑模运算）
题目描述
给定两个整数 n 和 k，我们需要计算由数字 1 到 n 组成的排列中，恰好包含 k 个逆序对的排列数目。逆序对的定义如下：在排列中，如果存在两个位置 i < j 且 a[i] > a[j]，则 (a[i], a[j]) 构成一个逆序对。
由于答案可能非常大，我们常常需要将结果对某个大质数（如 10^9 + 7）取模后输出。
这是一个经典的计数类线性动态规划问题。与基础的“K个逆序对数组”相比，进阶版可能需要处理更大的 n 和 k 值，并要求算法在时间和空间上高效。
例子
- 输入：n = 3, k = 1
- 输出：2
- 解释：由数字 1,2,3 组成的排列中，恰好有1个逆序对的排列是 [1,3,2] 和 [2,1,3]。
解题过程
我们将问题分解为若干步骤，从暴力解法逐步优化到动态规划解法，最后进行空间优化。
步骤1：理解问题与暴力解（不可行）
我们可以枚举所有 n! 个排列，对每个排列计算逆序对数量（计算逆序对可用归并排序的思想在 O(n log n) 完成），统计恰好有 k 个逆序对的排列数。但 n 最大可达 1000 甚至更大，n! 是天文数字，暴力法完全不现实。因此我们必须寻找更高效的方法。
步骤2：动态规划状态定义
动态规划的核心在于找到子问题。我们可以从 1 到 n 逐个插入数字来构造排列，并利用逆序对的性质。
考虑这样一个过程：我们已经用数字 1 到 i-1 构造了所有排列，现在要插入数字 i。数字 i 是当前最大的数字，如果将它插入到一个已有排列的第 j 个位置（0-indexed，从末尾开始计数），它就会与它后面的 j 个数字形成逆序对（因为数字 i 比之前所有数字都大）。例如：
- 已有排列 [2,1,3]（用数字1~3，但这里i=4），插入数字4：
- 插入到末尾（j=0）：[2,1,3,4] → 新增0个逆序对。
- 插入到倒数第二（j=1）：[2,1,4,3] → 新增1个逆序对（4>3）。
- 插入到倒数第三（j=2）：[2,4,1,3] → 新增2个逆序对（4>1, 4>3）等等。
因此，如果我们定义 dp[i][k] 表示用数字 1 到 i 组成的排列中，恰好有 k 个逆序对的排列数量，那么我们可以从 dp[i-1][*] 推导 dp[i][k]。
状态转移方程：
当我们要得到 dp[i][k]，考虑数字 i 插入到由数字1~i-1构成的某个排列中。插入位置可以是末尾（新增0个逆序对）、倒数第二个（新增1个）、…、最前面（新增 i-1 个）。所以：
dp[i][k] = sum_{j=0}^{i-1} dp[i-1][k - j]，其中 k-j >= 0。
也就是说，dp[i][k] 是 dp[i-1][k], dp[i-1][k-1], ..., dp[i-1][k-(i-1)] 的和（只要索引非负）。
初始条件：
dp[1][0] = 1（只有一个数字1，逆序对为0），dp[1][k>0] = 0。
dp[i][0] = 1（数字1~i的递增排列，逆序对为0）。
目标：求 dp[n][k]。
步骤3：直接DP实现与复杂度分析
我们可以用二维数组 dp[i][k] 来实现上述转移。i 从 2 到 n，k 从 0 到目标K（实际上最大逆序对数为 n*(n-1)/2，但我们可以限制在所需K）。
对于每个 i 和 k，我们累加 j 从 0 到 i-1 的 dp[i-1][k-j]。这需要 O(i) 时间，总时间复杂度为 O(n * k * n) = O(n^2 * k)，在 n 和 k 较大时（如 n=1000, k=1000）会超时（10^9操作）。我们需要优化。
步骤4：优化转移——前缀和
观察转移方程：
dp[i][k] = dp[i-1][k] + dp[i-1][k-1] + ... + dp[i-1][k-(i-1)]，且 k-j >= 0。
这实际上是在求 dp[i-1][] 在一个区间内的和。我们可以用前缀和（prefix sum）来优化，将内层循环的 O(i) 降到 O(1)。
定义前缀和数组 pref[i-1][x] = sum_{t=0}^{x} dp[i-1][t]，则：
dp[i][k] = pref[i-1][k] - pref[i-1][k-i]（如果 k-i >= 0）或 pref[i-1][k]（如果 k-i < 0）。注意：当 k-i < 0 时，我们只从 dp[i-1][0] 累加到 dp[i-1][k] 即可，即 pref[i-1][k]。
更精确地：
设 sum_{j=0}^{i-1} dp[i-1][k-j] 的有效 j 满足 k-j >= 0，即 j <= k。所以 j 的上限是 min(i-1, k)。那么：
dp[i][k] = pref[i-1][k] - (k-i >= 0 ? pref[i-1][k-i] : 0)。
验证：当 k >= i 时，我们需要从 dp[i-1][k-(i-1)] 累加到 dp[i-1][k]，也就是 pref[i-1][k] - pref[i-1][k-i]。
当 k < i 时，我们需要从 dp[i-1][0] 累加到 dp[i-1][k]，就是 pref[i-1][k]（此时 pref[i-1][k-i] 不存在，当作0）。
因此转移方程可写成：
dp[i][k] = pref[i-1][k] - (k-i >= 0 ? pref[i-1][k-i] : 0)。
前缀和的计算：
计算完 dp[i][k] 后，我们可以计算新的前缀和 pref[i][k] = pref[i][k-1] + dp[i][k]（对于 k=0..Kmax）。
这样，对于每个 i 和 k，我们可以在 O(1) 时间内计算 dp[i][k]，总时间复杂度为 O(n * k)。空间复杂度 O(n * k)。
步骤5：空间优化
注意到 dp[i][] 只依赖于 dp[i-1][]，因此我们可以用滚动数组优化，只保留两行（上一行和当前行）。进一步，前缀和数组也可以滚动更新。
我们定义 dp_prev 为上一行的 dp 值（即 dp[i-1][*]），pref_prev 为上一行的前缀和。然后计算当前行的 dp_cur 和 pref_cur。
实际上，我们可以直接用一个二维数组 dp[2][K+1] 和前缀和 pref[2][K+1] 来交替使用。但更常见的写法是只用一维数组 dp[k] 表示当前行的 dp 值，并用另一个一维数组 prev_prefix[k] 存储上一行的前缀和。
算法步骤：
- 初始化 dp_prev[0] = 1，其余为0。pref_prev[0] = 1，pref_prev[1..K] = 1（因为 dp_prev[>0]=0，所以前缀和均为1）。
- 对于 i 从 2 到 n：
- 对于 k 从 0 到 K：
dp_cur[k] = (pref_prev[k] - (k-i >= 0 ? pref_prev[k-i] : 0)) mod MOD。 - 计算 pref_cur[0] = dp_cur[0]，然后对于 k=1..K：pref_cur[k] = (pref_cur[k-1] + dp_cur[k]) mod MOD。
- 将 dp_cur 和 pref_cur 复制到 dp_prev 和 pref_prev 用于下一轮（或交换指针）。
- 对于 k 从 0 到 K：
- 最终答案 = dp_prev[k]（即 dp[n][k]）。
边界处理：
- 当 k 大于最大可能逆序对数 n*(n-1)/2 时，答案为0。
- 注意取模时，减法可能产生负数，需要加 MOD 再取模。
步骤6：实例演算
以 n=3, k=1 为例：
初始化：i=1，dp_prev = [1,0,0,...]，pref_prev = [1,1,1,...]（K=1）。
i=2：
- k=0: dp_cur[0] = pref_prev[0] - (0-2>=0?pref_prev[-2]:0) = 1 - 0 = 1。
- k=1: dp_cur[1] = pref_prev[1] - (1-2>=0?pref_prev[-1]:0) = 1 - 0 = 1。
计算 pref_cur: [1, 2]。
更新 dp_prev=[1,1], pref_prev=[1,2]。
i=3： - k=0: dp_cur[0] = pref_prev[0] - (0-3>=0?..) = 1 - 0 = 1。
- k=1: dp_cur[1] = pref_prev[1] - (1-3>=0?..) = 2 - 0 = 2。
计算 pref_cur: [1, 3]。
答案 dp_prev[1] = 2，与例子一致。
步骤7：复杂度与总结
- 时间复杂度：O(n * k)，因为有两层循环。
- 空间复杂度：O(k)，因为我们只用了一维数组存储 dp 和前缀和。
关键点：
- 利用插入最大数 i 时新增逆序对的数量等于插入位置从末尾计数的偏移量。
- 用前缀和优化区间求和，将内层循环降为 O(1)。
- 滚动数组节省空间。
这个进阶问题考察了对逆序对生成过程的理解、动态规划状态设计、以及前缀和优化技巧。通过上述步骤，我们可以高效计算出恰好有 k 个逆序对的排列数，并适用于 n 和 k 达到几千的规模（注意 k 最大约为 n^2/2，但通常题目会限制 k 在可接受范围）。