এই সমস্যায়, আমাদের দুটি ধনাত্মক সংখ্যা n এবং m (n <= m) দেওয়া আছে যা যথাক্রমে দুটি সেটের মোট আইটেম সংখ্যা নির্দেশ করে। আমাদের কাজ হল এই সেটগুলোর আইটেম থেকে জোড়া (এক বা একাধিক) নির্বাচন করার মোট পদ্ধতির সংখ্যা খুঁজে বের করা।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
2 2
আউটপুট
6
ব্যাখ্যা
আমাদের দুটি সেট আছে যedir দুটো উপাদান
সেট A = {1, 2} সেট B = {3, 4}
একটি জোড়া একবারে সাজানোর পদ্ধতি, (1..3), (1...4), (2..3), (2...4)
দুটি জোড়া একবারে সাজানোর পদ্ধতি, (1...3, 2...4) , (1...4, 2...3)
এই সমস্যাটি সমাধান করতে, আমরা সেটগুলোর উপাদানগুলোর কম্বিনেশন ব্যবহার করব। নিচে একটি সহজ কম্বিনেশন সূত্র দেওয়া আছে যা গণনা করতে পারে।
Ways = Σ^n i=1^n Ci * mCi * i! = Σ^n_i=1 ( ^nP_i * ^mP_i) / i
আমাদের সমাধানের বাস্তবায়ন দেখানোর প্রোগ্রাম,
উদাহরণ
#include <iostream> using namespace std; int* fact, *inverseMod; const int mod = 1e9 + 7; int power(int x, int y, int p){ int res = 1; x = x % p; while (y) { if (y & 1) res = (1LL * res * x) % p; y = y >> 1; x = (1LL * x * x) % p; } return res; } void calculate(int n){ fact[0] = inverseMod[0] = 1; for (int i = 1; i <= n; ++i) { fact[i] = (1LL * fact[i - 1] * i) % mod; inverseMod[i] = power(fact[i], mod - 2, mod); } } int nPr(int a, int b) { return (1LL * fact[a] * inverseMod[a - b]) % mod; } int selectPairCount(int n, int m){ fact = new int[m + 1]; inverseMod = new int[m + 1]; calculate(m); int ans = 0; for (int i = 1; i <= n; ++i) { ans += (1LL * ((1LL * nPr(n, i) * nPr(m, i)) % mod) * inverseMod[i]) % mod; if (ans >= mod) ans %= mod; } return ans; } int main() { int n = 2, m = 2; cout<<"জোড়া নির্বাচন করার পদ্ধতির সংখ্যা : "<<selectPairCount(n, m); return 0; }
আউটপুট
জোড়া নির্বাচন করার পদ্ধতির সংখ্যা : 6
