समस्या विवरण
हमें एक चर num दिया गया है। लक्ष्य संख्याओं [1, num] के उन क्रमचयों की गणना करना है जो पहले घटते हैं फिर बढ़ते हैं।
उदाहरण: num = 3 के लिए संख्याएँ 1,2,3 हैं। वैध क्रमचय: [3,1,2] और [2,1,3]। गणना = 2।
मुख्य अंतर्दृष्टि
हर क्रमचय में घटते से बढ़ते क्रम का परिवर्तन सबसे छोटी संख्या 1 की स्थिति से तय होता है। 1 के बाद संख्याएँ बढ़नी शुरू होती हैं।
- यदि 1 शुरुआत में है → पूरी तरह बढ़ता क्रम
- यदि 1 अंत में है → पूरी तरह घटता क्रम
- वैध क्रमचय के लिए 1 दूसरी से (num-1)वीं स्थिति के बीच होना चाहिए
गणितीय सूत्र
num = 4 के लिए:
- 1 को दूसरी स्थिति में रखें: 3C1 = 3 तरीके
- 1 को तीसरी स्थिति में रखें: 3C2 = 3 तरीके
- कुल = 6
सामान्यतः: count = x-1C1 + x-1C2 + ... + x-1Cx-2 = 2x-1 - 2
उदाहरण
इनपुट: num = 4 → आउटपुट: 6
इनपुट: num = 6 → आउटपुट: 30
दृष्टिकोण
द्विपद प्रमेय का उपयोग करके सीधे सूत्र 2^(num-1) - 2 से गणना करें। मॉड्यूलो 109+7 का उपयोग करें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long power(long long base, long long exp) {
long long result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return result;
}
int permutations_increase_decrease(int num) {
if (num == 1) return 0;
int count = (power(2, num - 1) - 2 + MOD) % MOD;
return count;
}
int main() {
int num = 4;
cout << "Count: " << permutations_increase_decrease(num);
return 0;
}
आउटपुट
Count: 6
