मान लीजिए कि हमारे पास बढ़ते क्रम में 1 से n तक n संख्याओं से युक्त एक सरणी है, तो हमें यह पता लगाना होगा कि यह कितनी गड़बड़ी उत्पन्न कर सकता है।
हम जानते हैं कि संयोजन गणित में, एक विचलन एक सेट के तत्वों का क्रमपरिवर्तन है, जैसे कि कोई भी तत्व अपनी मूल स्थिति में प्रकट नहीं होगा। उत्तर बहुत बड़ा हो सकता है, इसलिए आउटपुट मोड 10^9 + 7 लौटाएं।
इसलिए, यदि इनपुट 3 जैसा है, तो आउटपुट 2 होगा, क्योंकि मूल सरणी [1,2,3] है। दो विकार [2,3,1] और [3,1,2] हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मी :=10^9 + 7
-
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
-
फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम
-
मुख्य विधि से निम्न कार्य करें
-
रिट:=0
-
यदि n 1 के समान है, तो -
-
वापसी 0
-
-
यदि n 2 के समान है, तो -
-
वापसी 1
-
-
आकार की dp सरणी परिभाषित करें (n + 1)
-
डीपी[2] :=1
-
इनिशियलाइज़ i :=3 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
-
dp[i] :=mul(i-1, add(dp[i - 2], dp[i - 1]))
-
-
वापसी डीपी [एन]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
class Solution {
public:
int findDerangement(int n) {
int ret = 0;
if (n == 1)
return 0;
if (n == 2)
return 1;
vector dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
}
return dp[n];
}
};
main(){
Solution ob;
cout<<(ob.findDerangement(3));
} इनपुट
3
आउटपुट
2