C++で2つの異なる集合から1つ以上のペアを選択する方法

この問題では、それぞれの集合の要素数を表す2つの正整数 n と m(n ≤ m)が与えられます。求めたいのは、これら2つの集合の要素から1つ以上のペアを選択する方法の総数です。

まず、具体例で問題を確認しましょう。

入力例

2 2

出力例

6

解説

2つの集合 A と B は、どちらも2つの要素を持っています。

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

ペアを1つだけ選ぶ場合は、(1, 3)、(1, 4)、(2, 3)、(2, 4) の 4通り。
ペアを2つ同時に選ぶ場合は、「(1, 3) と (2, 4)」「(1, 4) と (2, 3)」の 2通りあります。

したがって、答えは 4 + 2 = 6通りとなります。

解法のアプローチ

この問題は、順列と組み合わせの公式を組み合わせることで効率的に解けます。「i 個のペアを選ぶ」場合について考えてみましょう。

• 集合Aから i 個の要素を選び、順番を付ける方法:nP_i 通り
• 集合Bから i 個の要素を選び、順番を付ける方法:mP_i 通り
• 同じペアの組が i! 回重複して数えられるため、最後に i! で割る

これを i = 1 から n まですべて足し合わせると、答えが得られます。

選び方 = Σ(i=1〜n) nCi × mCi × i!
       = Σ(i=1〜n) ( nPi × mPi ) / i!

非常に大きな数を扱うため、計算結果は 10⁹ + 7 で割った余りで管理します。また、割り算の代わりにフェルマーの小定理を利用して i! のモジュラ逆元を求めるのがポイントです。

C++での実装例

#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

コードのポイント

• power関数:繰り返し二乗法により、x^y mod p を高速に計算します。
• calculate関数:階乗(fact)とそのモジュラ逆元(inverseMod)を事前に一括計算しておきます。
• nPr関数:順列 nPk を「fact[n] × inverseMod[n−k]」として即座に求められます。
• selectPairCount関数:公式に沿って i = 1 から n まで答えを累積していきます。

この実装では、階乗の前計算に O(m)、メインの集計ループに O(n) しかかからないため、全体の時間計算量は O(n + m) と非常に効率的です。競技プログラミングでも頻出のテクニックなので、ぜひ覚えておきましょう。