给出两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下:对于数组的第i个和第 j个元素,如果满i < j且 a[i] > a[j],则其为一个逆序对;否则不是。
由于答案可能很大,只需要返回 答案 mod 109 + 7 的值。
不会做,直接学习题解代码:
1 class Solution { 2 private: 3 static constexpr int mod = 1000000007; 4 5 public: 6 int kInversePairs(int n, int k) { 7 vector<vector<int>> f(2, vector<int>(k + 1)); 8 f[0][0] = 1; 9 for (int i = 1; i <= n; ++i) { 10 for (int j = 0; j <= k; ++j) { 11 int cur = i & 1, prev = cur ^ 1; 12 f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j]; 13 if (f[cur][j] >= mod) { 14 f[cur][j] -= mod; 15 } 16 else if (f[cur][j] < 0) { 17 f[cur][j] += mod; 18 } 19 } 20 } 21 return f[n & 1][k]; 22 } 23 };