629_K个逆序对数组_2021.11.11(困难)

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

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

由于答案可能很大,只需要返回 答案 mod 109 + 7 的值。

629_K个逆序对数组_2021.11.11(困难)

 

 不会做,直接学习题解代码:

 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 };

 

上一篇:CVE-2019-0708:RDP终极EXP复现


下一篇:jQuery的方法以及一些用法