এই সমস্যায়, আমাদের দুটি ধনাত্মক সংখ্যা n এবং m (n <=m) দেওয়া হয়েছে যা যথাক্রমে দুটি সেটের মোট আইটেম সংখ্যা। আমাদের কাজ হল এই সেটগুলির আইটেমগুলি থেকে জোড়া (এক বা একাধিক) নির্বাচন করার মোট উপায় খুঁজে বের করা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট
2 2
আউটপুট
6
ব্যাখ্যা
আমাদের কাছে দুটি উপাদান আছে দুটি সেট আছে
Set A = {1, 2}
Set B = {3, 4} একবারে এক জোড়া সাজানোর উপায়,(1..3), (1...4), (2..3), (2...4)
একসাথে দুটি জোড়া সাজানোর উপায়,(1...3, 2...4), (1...4, 2...3)
এই সমস্যাটি সমাধান করতে, আমরা সেটের উপাদানগুলির সংমিশ্রণ ব্যবহার করব। নিম্নলিখিতটি একটি সাধারণ সমন্বয় সূত্র যা গণনা খুঁজে পেতে পারে।
Ways = Σn i=1n Ci* mCi* i! = Σni=1 ( nPi * mPi) /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<<"The number of ways to select pairs is : "<<selectPairCount(n, m);
return 0;
} আউটপুট
The number of ways to select pairs is : 6
