मान लीजिए हमारे पास दो पूर्णांक 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