मान लीजिए हमारे पास 1 से n तक बढ़ते क्रम में n संख्याओं वाली एक सरणी है, हमें यह ढूंढना है कि यह कितने डीरेंजमेंट उत्पन्न कर सकती है।
हम जानते हैं कि संयोजन गणित में, एक डीरेंजमेंट एक समुच्चय के तत्वों का एक क्रमपरिवर्तन है, जैसे कि कोई तत्व अपनी मूल स्थिति में प्रकट नहीं होगा। उत्तर बहुत बड़ा हो सकता है, इसलिए आउटपुट को 10^9 + 7 से मॉड्यूलो करें।
उदाहरण के लिए, यदि इनपुट 3 है, तो आउटपुट 2 होगा, क्योंकि मूल सरणी [1,2,3] है। दो डीरेंजमेंट [2,3,1] और [3,1,2] हैं।
हल करने की विधि
हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- m = 10^9 + 7।
add()औरmul()फ़ंक्शन मॉड्यूलर अंकगणित के लिए।- यदि n == 1, तो 0 लौटाएं।
- यदि n == 2, तो 1 लौटाएं।
- आकार n+1 की dp सरणी परिभाषित करें।
- dp[2] = 1।
- i = 3 से n तक: dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]))।
- dp[n] लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
