题目描述

[HARD]

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7.

Example 1:

1
2
3
Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

1
2
3
Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

思路

1 问题建模与 DP 状态

定义
令 dp[i][j] 表示：用数字 1..i 组成的所有排列中，恰好有 j 个逆序对的排列个数。

目标
求 dp[n][k]，并对 1e9+7 取模。

直觉
从 i-1 个数扩展到 i 个数时，把新数 i 插入到某个位置。由于 i 是当前最大的数，它与它右边的每一个元素都形成一个逆序对。因此，若把 i 放到从右数的第 x 个位置（也就是在末尾右侧有 x 个元素在它右边），就会新增加 x 个逆序对，其中 x ∈ [0, i-1]。

于是：

$$
dp[i][j] = \sum_{x=0}^{min(j, i-1)} dp[i-1][j - x]
$$

这就是核心转移。

2 优化

前缀和优化

直接按上式求和，每个 dp[i][j] 要枚举 x，代价是 O(i)，总体会到 O(n * k * n)（或最坏到 O(n * k * k)），会超时。

观察到这其实是一个滑动窗口和：

当 j < i 时，窗口是 [0..j]，
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + … + dp[i-1][0]

当 j ≥ i 时，窗口是长度为 i 的区间 [j-(i-1) .. j]，
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + … + dp[i-1][j-(i-1)]

用前缀和 prefix[j] = dp[i-1][0] + … + dp[i-1][j]，就能 O(1) 得到区间和：

j < i：dp[i][j] = prefix[j]

j ≥ i：dp[i][j] = prefix[j] - prefix[j - i]

这正是代码里两段分支的含义。

为防止 C++ 负数取模的问题，代码使用

1
((prefix[j] - prefix[j-i]) % MOD + MOD) % MOD

先加一次 MOD 再 %MOD，保证非负。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:

    const int MOD = 1000000007;

    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));

        dp[0][0] = 1; // Base case: 1 way to have 0 inverse pairs with 0 elements

        for(int i = 1; i <=n; i++){
            vector<int> prefix(k+1, 0);
            prefix[0] = dp[i-1][0];

            for(int j = 1; j <= k; j++){
                prefix[j] = (prefix[j-1] + dp[i-1][j]) % MOD;
            }

            for(int j = 0; j <= k; j++){
                if(j >= i) {
                    dp[i][j] = ((prefix[j] - prefix[j-i])% MOD + MOD) % MOD; // Subtract the prefix sum that exceeds the current i
                } else {
                    dp[i][j] = prefix[j]; // Use the prefix sum directly
                }
            }
        }

        return dp[n][k];

    }
};