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 सरणी 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 m
  - यदि j>=i, तो −
    - dp[i, j] :=(dp[i, j] - dp[i – 1, j - i] + m) मॉड m
रिटर्न डीपी[एन, के]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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