วิธีเลือกหนึ่งคู่หรือมากกว่าจากสองชุดที่แตกต่างกันใน C++

ในปัญหานี้ เราได้รับตัวเลขบวกสองตัว n และ m (n <=m) ซึ่งเป็นจำนวนรวมของรายการของสองชุดตามลำดับ งานของเราคือค้นหาจำนวนวิธีทั้งหมดในการเลือกคู่ (อย่างน้อยหนึ่งรายการ) จากรายการของชุดเหล่านี้

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

2 2

ผลลัพธ์

6

คำอธิบาย

เรามีสองชุดที่มีสององค์ประกอบ

Set A = {1, 2}
Set B = {3, 4}

วิธีจัดเรียงทีละคู่,(1..3), (1...4), (..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