K Inverse Pairs Array ใน C++

สมมติว่าเรามีจำนวนเต็ม n และ k สองจำนวน เราต้องหาจำนวนอาร์เรย์ที่ประกอบด้วยตัวเลขตั้งแต่ 1 ถึง n จำนวนเท่าใดจึงจะมีคู่ผกผัน k คู่พอดี คู่ผกผันสำหรับองค์ประกอบ ith และ jth ในอาร์เรย์ ถ้า i a[j] จะเรียกว่าคู่ผกผัน ที่นี่คำตอบอาจมีขนาดใหญ่มาก คำตอบควรเป็น modulo $10^{9}$ + 7

ดังนั้นหากอินพุตเป็น n =3 และ k =1 เอาต์พุตจะเป็น 2 เนื่องจากอาร์เรย์ [1,3,2] และ [2,1,3] จะมีคู่ผกผันเพียงคู่เดียว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (k + 1)
dp[0, 0] :=1
สำหรับการเริ่มต้น i :=1 เมื่อ i<=n อัปเดต (เพิ่ม i โดย 1) ทำ −
- dp[i, 0] :=1
- สำหรับการเริ่มต้น j :=1 เมื่อ j <=k อัปเดต (เพิ่ม j ทีละ 1) ทำ −
  - dp[i, j] :=dp[i, j - 1] + dp[i – 1, j]
  - dp[i, j] :=dp[i, j] mod ม
  - ถ้า j>=i แล้ว −
    - dp[i, j] :=(dp[i, j] - dp[i – 1, j - i] + m) mod ม.
ส่งคืน dp[n, k]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

4
2

K Inverse Pairs Array ใน C++

ตัวอย่าง

อินพุต

ผลลัพธ์