Số cách chọn một hoặc nhiều cặp từ hai tập hợp khác nhau trong C++

Trong bài toán này, chúng ta được cho hai số dương n và m (n <= m) là tổng số phần tử của hai tập hợp tương ứng. Nhiệm vụ là tìm tổng số cách chọn các cặp (một hoặc nhiều) từ các phần tử của các tập hợp này.

Hãy xem ví dụ để hiểu bài toán,

Đầu vào

2 2

Đầu ra

6

Giải thích

Chúng ta có hai tập hợp đều có hai phần tử

Tập A = {1, 2} Tập B = {3, 4}

Cách sắp xếp một cặp tại một thời điểm, (1..3), (1...4), (2..3), (2...4)

Cách sắp xếp hai cặp tại một thời điểm, (1...3, 2...4) , (1...4, 2...3)

Để giải bài toán này, chúng ta sẽ sử dụng tổ hợp của các phần tử của các tập hợp. Sau đây là công thức tổ hợp đơn giản có thể tìm số lượng.

Ways = Σn i=1n Ci* mCi* i! = Σni=1 ( nPi * mPi) /i

Chương trình triển khai giải pháp,

Ví dụ

#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<<"Số cách chọn cặp là : "<<selectPairCount(n, m);    return 0; }

Đầu ra

Số cách chọn cặp là : 6