# 629.K个逆序对数组 (Hard)

## 问题描述
[629. K个逆序对数组 (Hard)](https://leetcode.cn/problems/k-inverse-pairs-array/)

给出两个整数 `n` 和 `k`，找出所有包含从 `1` 到 `n` 的数字，且恰好拥有 `k`
个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第 `i` 个和第 `j` 个元素，如果满 `i` < `j` 且 `a[i]` >
`a[j]`，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 10 \+ 7 的值。

**示例 1:**

```
输入: n = 3, k = 0
输出: 1
解释:
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

```

**示例 2:**

```
输入: n = 3, k = 1
输出: 2
解释:
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

```

**说明:**

1. `n` 的范围是 \[1, 1000\] 并且 `k` 的范围是 \[0, 1000\]。

## 解题思路
像这种答案需要取模的题，解题思路一般都是动态规划；

以`dp[n][k]`表示考虑前$n$个数时，逆序对刚好为$k$个的方案数，为了找到递推关系，我们需要考虑数$n$的位置，假设数$n$位于第$n$个位置，那么`dp[n][k] = dp[n - 1][k]`（因为没有数能与$n$组成逆序对，相当于不用考虑数$n$），假设数$n$位于第$n - 1$个位置，那么`dp[n][k] = dp[n - 1][k - 1]`，所以，我们可以求得递推关系：
- 当`k >= n - 1`时，$dp[n][k] = \sum\limits_{i=0}^{n-1}dp[n-1][k-i]$
- 当`k < n - 1`时，$dp[n][k] = \sum\limits_{i=0}^{k}dp[n][i]$

但是直接用这个递推关系式，时间复杂度为$O(nk^2)$，可能会超时，我们考虑用$dp[n][k] - dp[n][k - 1]$，可以发现新的递推关系式：
- 如果`k <= n - 1`，$dp[n][k] = dp[n][k - 1] + dp[n - 1][k]$
- 如果`k > n - 1`，$dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n]$

## 代码
```cpp
class Solution {
  public:
    int kInversePairs(int n, int k) {
        vector<vector<long>> dp(n + 1, vector<long>(k + 1, 0));
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = 1;
        }
        int mod = 1000000007;
        if (k > n * (n - 1) / 2) {
            return 0;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k && j <= (i * (i - 1) / 2); ++j) {
                if (j <= i - 1) {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - i] + mod) % mod;
                }
            }
        }
        return dp[n][k];
    }
};
```