จำนวนวิธีเลือกคู่หนึ่งขึ้นไปจากเซตสองเซตที่ต่างกันใน C++

ในโจทย์นี้ เราได้รับจำนวนบวกสองจำนวน 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)

เพื่อแก้ปัญหานี้ เราจะใช้การจัดหมู่ (combinations) ขององค์ประกอบของเซต สูตรการจัดหมู่ง่ายๆ ด้านล่างสามารถหาจำนวนได้:

Ways = Σᵢ₌₁ⁿ (ⁿCᵢ * ᵐCᵢ * i!) = Σᵢ₌₁ⁿ (ⁿPᵢ * ᵐPᵢ) / 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