Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में व्युत्क्रम जोड़ी सरणी (K Inverse Pairs Array)


मान लीजिए हमारे पास दो पूर्णांक n और k हैं, हमें ज्ञात करना है कि 1 से n तक की संख्याओं से बनी कितनी अलग-अलग सरणियां हैं जिनमें ठीक k व्युत्क्रम जोड़े (inverse pairs) हैं। व्युत्क्रम जोड़ी सरणी में i-वें और j-वें तत्व के लिए है, यदि i < j और a[i] > a[j] तो इसे व्युत्क्रम जोड़ी कहा जाता है। यहां उत्तर बहुत बड़ा हो सकता है, उत्तर मॉड्यूलो $10^9$ + 7 होना चाहिए।

तो यदि इनपुट n = 3 और k = 1 जैसा है, तो आउटपुट 2 होगा क्योंकि सरणी [1,3,2] और [2,1,3] में केवल एक व्युत्क्रम जोड़ी होगी।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -

  • आकार (n + 1) x (k + 1) का एक 2D ऐरे dp परिभाषित करें
  • dp[0, 0] := 1
  • i := 1 से प्रारंभ करें, जब i <= n, i बढ़ाते हुए, करें -
    • dp[i, 0] := 1
    • j := 1 से प्रारंभ करें, जब j <= k, j बढ़ाते हुए, करें -
      • 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

आउटपुट

5

  1. - C++ में Switch स्टेटमेंट: एक पूर्ण गाइड

    C++ में Switch स्टेटमेंट का उपयोग कैसे करें कंडीशनल स्टेटमेंट्स सभी प्रोग्रामिंग भाषाओं की एक सामान्य विशेषता हैं। इन स्टेटमेंट्स का उपयोग प्रोग्राम के प्रवाह को नियंत्रित करने और यह निर्दिष्ट करने के लिए किया जाता है कि कोड के विशिष्ट ब्लॉक्स कब निष्पादित होने चाहिए। C++ में उपयोग किए जाने वाले मुख

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस