K Inverse Pairs Array trong C ++

Giả sử chúng ta có hai số nguyên n và k, chúng ta phải tìm bao nhiêu mảng khác nhau gồm các số từ 1 đến n sao cho có đúng k cặp nghịch đảo. Cặp nghịch đảo dành cho phần tử thứ i và thứ j trong mảng, nếu i a [j] thì được gọi là cặp nghịch đảo. Ở đây, câu trả lời có thể rất lớn, câu trả lời phải là modulo $ 10 ^ {9} $ + 7.

Vì vậy, nếu đầu vào là n =3 và k =1, thì đầu ra sẽ là 2 vì mảng [1,3,2] và [2,1,3] sẽ chỉ có một cặp nghịch đảo.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một dp mảng 2D có kích thước (n + 1) x (k + 1)
• dp [0, 0]:=1
• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
  • dp [i, 0]:=1
  • để khởi tạo j:=1, khi j <=k, cập nhật (tăng j lên 1), thực hiện -
    • dp [i, j]:=dp [i, j - 1] + dp [i - 1, j]
    • dp [i, j]:=dp [i, j] mod m
    • nếu j> =i, thì -
      • dp [i, j]:=(dp [i, j] - dp [i - 1, j - i] + m) mod m
• trả về dp [n, k]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
   int kInversePairs(int n, int k) {
      vector < vector <int> > dp(n + 1, vector <int>(k + 1));
      dp[0][0] = 1;
      for(int i = 1; i <= n; i++){
         dp[i][0] = 1;
         for(int j = 1; j <= k; j++){
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            dp[i][j] %= m;
            if(j >= i){
               dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m;
            }
         }
      }
      return dp[n][k];
   }
};
main(){
   Solution ob;
   cout << (ob.kInversePairs(4,2));
}

Đầu vào

4
2

Đầu ra

5