이 문제에서는 두 개의 양수 n과 m(n ≤ m)이 주어지며, 각각 두 집합에 속한 원소의 총 개수를 나타냅니다. 목표는 이 두 집합의 원소들로부터 하나 이상의 쌍(pair)을 선택하는 방법의 총 개수를 구하는 것입니다.
문제 이해를 위한 예시
입력
2 2
출력
6
설명
두 집합은 각각 두 개의 원소를 가지고 있습니다.
집합 A = {1, 2}
집합 B = {3, 4}한 번에 한 쌍씩 선택하는 방법은 다음과 같습니다. (1, 3), (1, 4), (2, 3), (2, 4)
한 번에 두 쌍씩 선택하는 방법은 다음과 같습니다. (1-3, 2-4), (1-4, 2-3)
따라서 가능한 모든 방법의 수는 4 + 2 = 6가지입니다.
해결 접근 방식
이 문제는 조합(combination)의 개념을 활용해 해결할 수 있습니다. 첫 번째 집합에서 i개의 원소를 고르고, 두 번째 집합에서도 i개의 원소를 고른 뒤, 선택된 원소들을 서로 짝지어 주는 순열(permutation)까지 고려하면 됩니다. 이를 일반화한 공식은 다음과 같습니다.
Ways = Σ(i=1 → n) nCi × mCi × i!
= Σ(i=1 → n) (nPi × mPi) / i!여기서 nCk는 조합, nPk는 순열을 의미합니다. 각 i에 대해 첫 번째 집합에서 i개를 뽑는 경우의 수와 두 번째 집합에서 i개를 뽑는 경우의 수를 곱한 뒤, 이들을 짝짓는 i!가지의 방법을 곱해주면 됩니다.
결과값이 매우 빠르게 커질 수 있으므로, 구현에서는 10⁹ + 7을 모듈러 값으로 사용해 오버플로우를 방지합니다. 또한 페르마의 소정리(Fermat's Little Theorem)를 활용해 모듈러 역원을 계산함으로써 나눗셈 연산을 안전하게 처리합니다.
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
복잡도 분석
시간 복잡도: O(m) — 팩토리얼과 모듈러 역원 테이블을 계산하는 데 O(m)이 걸리며, 메인 루프는 최대 n(≤ m)번 반복되므로 전체 시간 복잡도는 O(m)입니다.
공간 복잡도: O(m) — 팩토리얼 배열과 모듈러 역원 배열을 저장하기 위해 크기 m+1의 두 개의 배열이 필요합니다.