C++-এ প্রথমে হ্রাসমান তারপর বৃদ্ধিমান অনুক্রমণীর গণনা

আমাদের একটি ভেরিয়েবল num দেওয়া আছে। লক্ষ্য হল [1, num] পরিসরের সংখ্যাগুলোর এমন অনুক্রমণী (permutation) বের করা যেগুলো প্রথমে হ্রাসমান তারপর বৃদ্ধিমান। উদাহরণস্বরূপ num=3 হলে সংখ্যাগুলো ১,২,৩। অনুক্রমণীগুলো: [3,1,2] এবং [2,1,3] — মোট ২টি।

প্রতিটি অনুক্রমণীতে হ্রাসমান থেকে বৃদ্ধিমান হওয়ার পরিবর্তন বিন্দু নির্ধারিত হয় সবচেয়ে ছোট সংখ্যা ১-এর অবস্থান থেকে। ১-এর পর থেকে সংখ্যাগুলো বৃদ্ধিমান হতে শুরু করে। একটি অনুক্রমণী প্রথমে হ্রাসমান তারপর বৃদ্ধিমান হবে যদি ১-द্বিতীয় অবস্থান থেকে (num-1)তম অবস্থানের মধ্যে থাকে।

যদি ১ প্রথমে থাকে → সম্পূর্ণ বৃদ্ধিমান।
যদি ১ শেষে থাকে → সম্পূর্ণ হ্রাসমান।

উদাহরণ

ইনপুট: num = 4

আউটপুট: ৬

ব্যাখ্যা:

১ দ্বিতীয় অবস্থানে: [2,1,3,4], [3,1,2,4], [4,1,2,3] → 3C1 = 3টি
১ তৃতীয় অবস্থানে: [2,3,1,4], [2,4,1,3], [3,4,1,2] → 3C2 = 3টি
মোট = 3 + 3 = 6

ইনপুট: num = 6

আউটপুট: ৩০

গাণিতিক সূত্র

যেকোনো x এর জন্য অনুক্রমণীর সংখ্যা = ^x-1C₁ + ^x-1C₂ + ... + ^x-1C_x-2 = 2^x-1 - 2 (বাইনোমিয়াল থিওরেম)।

অ্যালগরিদম

1. num ইনপুট নিন।
2. permutations_increase_decrease(int num) ফাংশনটি ফলাফল ফেরত দেবে।
3. value(long long i, long long num) ফাংশনটি (i^num) % MOD হিসাব করে। এখানে MOD = 1000000007।
4. যদি num == 1 হয় তবে ০ ফেরত দিন।
5. অন্যথায় count = (value(2, num - 1) - 2) % MOD হিসাব করুন।
6. ফলাফল ফেরত দিন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

long long value(long long i, long long num) {
    const int MOD = 1000000007;
    if (num == 0) return 1;
    long long j = value(i, num / 2) % MOD;
    j = (j * j) % MOD;
    if (num & 1) j = (j * i) % MOD;
    return j;
}

int permutations_increase_decrease(int num) {
    const int MOD = 1000000007;
    if (num == 1) return 0;
    int count = (value(2, num - 1) - 2) % MOD;
    if (count < 0) count += MOD;
    return count;
}

int main() {
    int num = 4;
    cout << "Count of permutations that are first decreasing then increasing are: " 
         << permutations_increase_decrease(num);
    return 0;
}

আউটপুট

Count of permutations that are first decreasing then increasing are: 6