C++ এ K বিপরীত জোড়া অ্যারে

ধরুন আমাদের দুটি পূর্ণসংখ্যা n এবং k আছে, আমাদের খুঁজে বের করতে হবে কতগুলি ভিন্ন অ্যারে 1 থেকে n পর্যন্ত সংখ্যা নিয়ে গঠিত যাতে ঠিক k বিপরীত জোড়া আছে। বিপরীত যুগলটি অ্যারের ith এবং jth উপাদানের জন্য, যদি i a[j] হয় তবে এটি একটি বিপরীত জোড়া বলা হয়। এখানে উত্তরটি অনেক বড় হতে পারে, উত্তরটি মডিউল হতে হবে $10^{9}$ + 7।

তাই যদি ইনপুটটি n =3 এবং k =1 এর মত হয়, তাহলে অ্যারে হিসাবে আউটপুট 2 হবে [1,3,2] এবং [2,1,3]-এ শুধুমাত্র একটি বিপরীত জোড়া থাকবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি 2D অ্যারে ডিপি আকারের (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 m
  - যদি j>=i, তারপর −
    - dp[i, j] :=(dp[i, j] - dp[i – 1, j - i] + m) mod m
রিটার্ন 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