সি++-এ বৃত্তাকার নোডগুলোর মধ্যে নন-ওভারল্যাপিং এজ দিয়ে সংযোগের উপায় সংখ্যা গণনা

সমস্যা বিবরণ

n সংখ্যক নোড বৃত্তাকারভাবে সাজানো আছে। n/2টি এজ দিয়ে সব নোডকে সংযুক্ত করতে হবে যাতে কোনো দুটি এজ একে অপরের সাথে ইন্টারসেক্ট না করে। উপায়ের সংখ্যা বের করুন (মড 10^9+7)।

উদাহরণ: n = 4 হলে আউটপুট 2।

সমাধানের পদ্ধতি

এটি ক্যাটালান সংখ্যা (Catalan Number) সমস্যা। n নোডের জন্য উত্তর হলো C(n/2)।

1. dp[i] = i জোড়া নোডের জন্য উপায় সংখ্যা।
2. dp[0] = 1, dp[1] = 1।
3. রিকারেন্স: dp[i] = Σ (2 * dp[j-1] * dp[i-j]) for j = 1 to i/2।
4. যদি i বিজোড় হয়, মিডল টার্ম যোগ করুন: dp[(i-1)/2]²।
5. মড 10^9+7 নিয়ে ক্যালকুলেট করুন।

উদাহরণ কোড

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

int solve(int n) {
    vector<long long> dp(n/2 + 1);
    dp[0] = 1; dp[1] = 1;
    int mod = 1000000007;
    for (int i = 2; i <= n/2; i++) {
        int high = i;
        dp[i] = 0;
        for (int j = 1; j <= high/2; j++)
            dp[i] = (dp[i] + 2 * dp[j-1] * dp[high-j]) % mod;
        if (high % 2)
            dp[i] = (dp[i] + dp[(high-1)/2] * dp[(high-1)/2]) % mod;
        dp[i] %= mod;
    }
    return dp[n/2];
}

int main() {
    int n = 4;
    cout << solve(n);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: 4

আউটপুট: 2