포함-배제의 원리

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다.

Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다.

포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다.

1) 집합이 두 개인 경우

$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다.

2) 집합이 세 개인 경우

세 개의 유한 집합 $A$, $B$, $C$가 있다고 하자. 이의 벤다이어그램은 위 그림과 같다. 세 집합의 합집합의 크기 $|A \cup B \cup C|$는 아래와 같이 계산할 수 있다.

3) 일반항

일반적으로 $n$개의 유한 집합 $A_1, A_2, \dots, A_n$이 있다고 하자. 그 합집합의 크기는 아래와 같다.

4) 여러 응용

문제) 완전 순열이란, 순열의 $k$번째 자리에 수 $k$가 오지 않도록 1부터 $n$까지의 수로 이루어진 크기가 $n$인 순열을 의미한다. 완전 순열의 크기 $n$에 대한 완전 순열의 개수의 일반항을 구해보자.

해법) $k$가 $k$번째 자리에 위치한 순열의 집합을 $P_k$라 하자. 완전 순열의 개수 $D_n$은 $n!$에 $|P_1 \cup P_2 \cup \dots \cup P_n|$ 을 뺀 값이 된다.

$D_n = \sum\limits_{k=0}^{n} {{(-1)}^{k}{n \choose k}{(n-k)!}} = n!\sum\limits_{k=0}^{n} \frac{{(-1)}^k}{k!}$ 이 된다.

문제) Codeforces Round #257 (Div. 1) D

해법) $P_i$를 and 연산 결과가 $i$를 비트로 포함하고 있는 경우의 수라고 정의하자. (여기서 $i$가 $k$에 비트로 포함된다라는 것은 $i \wedge k = i$) 그러면 최종 답은 $\sum\limits_{i=0}^{2^{20}-1} {{(-1)}^{b_i} P_i}$가 된다. (여기서 $b_i$는 $i$에 있는 1의 비트의 개수) $P_i$를 계산하기 위해 $A_i$를 $n$개의 수 중에 $i$를 포함하고 있는 개수라고 정의하자. 그러면 $P_i = {2}^{A_i}-1$이 된다.

#include <stdio.h> #define MAXN 1048576 #define bit(n) (1<<(n)) const int MOD = 1e9 + 7; int N,A[MAXN],P[MAXN]={1},ans; int main() { int i,j,k; scanf("%d",&N); for (i=1;i<=N;i++){ scanf("%d",&k), A[k]++; P[i] = P[i-1]<<1; if (P[i] >= MOD) P[i] -= MOD; } for (j=0;j<20;j++){ for (i=bit(20);--i;) if (i&bit(j)){ k = i^bit(j); A[k] += A[i]; if (A[k] >= MOD) A[k] -= MOD; } } for (i=0;i<bit(20);i++){ int cnt=0,v=P[A[i]]-1; if (v < 0) v += MOD; for (j=0;j<20;j++) if (i&bit(j)) cnt++; if (cnt&1){ ans -= v; if (ans < 0) ans += MOD; } else{ ans += v; if (ans >= MOD) ans -= MOD; } } printf("%d\n",ans); }

문제) Codeforces Round #258 (Div. 2) E

해법) 전체 집합 $U$를 각 상자에 몇 개의 꽃이 들어있는지와 상관 없이 합이 $s$가 되는 경우들의 집합이라고 하자. 집합 $A_i$를 $i$번째 상자에 가능한 꽃의 개수를 초과하여 합이 $s$가 되는 경우들의 집합이라고 하고, 답은 $|U - \bigcup\limits^{n}_{i=1} A_i|$ 이 된다. 이를 포함과 배제의 원리를 이용하여 구하면 된다.

추가적으로 $n$개의 상자에서 임의의 개수에 꽃을 뽑아 합이 $s$가 되는 경우의 수는 $_{s+1}H_{n-1} = {s+n-1 \choose n-1}$이 된다.

#include <stdio.h> #define bit(n) (1<<(n)) typedef long long lld; const int MOD = 1e9 + 7; int N; lld S,A[20]; int inv[20]; int ans; int inv_(int n) { int ret = 1, m = MOD-2, v = n; for (;m;m>>=1,v=(lld)v*v%MOD) if (m&1){ ret = (lld)ret*v%MOD; } return ret; } int calc(lld s) { if (s < 0) return 0; lld n = s+N-1, r = N-1; int ret = 1; for (lld i=n;i>n-r;i--) ret = (lld)ret*(i%MOD)%MOD; for (int i=2;i<=r;i++) ret = (lld)ret*inv[i]%MOD; return ret; } int main() { int i,j; scanf("%d%lld",&N,&S); for (i=2;i<N;i++) inv[i] = inv_(i); for (i=0;i<N;i++) scanf("%lld",A+i); for (i=0;i<bit(N);i++){ int cnt = 0; lld s = S; for (j=0;j<N;j++) if (i&bit(j)){ cnt++; s -= A[j]+1; } int v = calc(s); if (cnt&1) ans = (ans-v+MOD)%MOD; else ans = (ans+v)%MOD; } printf("%d\n",ans); }