포함-배제 원리는 어떤 집합의 크기를 세거나 복잡한 사건의 확률을 계산할 수 있게 해 주는 중요한 조합론적 기법입니다.
포함-배제 원리의 공식화 언어적 공식화 포함-배제 원리는 다음과 같습니다:
여러 집합의 합집합의 크기를 구하려면, 먼저 각 집합의 크기를 모두 더한 다음, 이 집합들의 모든 두 집합 쌍의 교집합의 크기를 빼고, 가능한 모든 세 집합 조합의 교집합의 크기를 다시 더하고, 네 집합 조합의 교집합의 크기를 빼는 식으로 모든 집합의 교집합에 이를 때까지 계속해야 합니다.
집합 용어를 이용한 정식화 앞에서 말로 설명한 정식화를 수학적 형태로 나타내면 다음과 같습니다:
\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n[…]
이는 부분집합에 대한 합을 이용하여 더 간결하게 쓸 수 있습니다. A_i를 원소로 하는 집합을 B라고 합시다. 그러면 포함-배제 원리는 다음과 같은 형태가 됩니다.
\left| \bigcup_{i=1}^n A_i \right| = \sum_{C \sub[…]
이 공식은 드무아브르(Abraham de Moivre)가 만든 것으로 알려져 있습니다.
벤 다이어그램을 이용한 정식화 다이어그램에 세 도형 A, B, C가 표시되어 있다고 합시다.
그러면 합집합 A \cup B \cup C의 넓이는 A, B, C의 넓이의 합에서 두 번 덮인 넓이 A \cap B, A \cap C, B \cap C를 빼고, 세 번 덮인 넓이 A \cap B \cap C를 더한 것과 같습니다:
S(A \cup B \cup C) = S(A) ~ + ~ S(B) ~ + ~ S(C) ~[…]
같은 방식으로 이를 n개 도형의 합집합으로도 일반화할 수 있습니다.
확률론의 용어로 표현한 정식화 A_i (i = 1 \ldots n)가 사건이고 {\cal P}(A_i)가 그 확률이라면, 이 사건들의 합사건의 확률(즉, 이 사건들 중 적어도 하나가 일어날 확률)은 다음과 같습니다:
\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n[…]
이 합은 사건 A_i를 원소로 하는 집합 B의 부분집합들에 대한 합의 형태로도 쓸 수 있습니다:
{\cal P} \left( \bigcup_{i=1}^n A_i \right) = \su[…]
포함-배제 원리의 증명 증명에는 집합론의 용어로 표현한 수학적 형태를 사용하는 것이 편리합니다:
\left| \bigcup_{i=1}^n A_i \right| = \sum_{C \sub[…]
여기서 B는, 다시 말하지만, A_i들로 이루어진 집합입니다.
집합 A_i 중 적어도 하나에 포함된 모든 원소가 공식에 의해 정확히 한 번 계산됨을 증명해야 합니다. (A_i 중 어느 것에도 포함되지 않은 나머지 원소들은 공식의 우변에 나타나지 않으므로 결코 계산될 수 없다는 점에 유의하십시오.)
정확히 k \ge 1개의 집합 A_i에 포함된 임의의 원소 x를 생각해 봅시다. 이 원소가 공식에 의해 정확히 한 번 세어진다는 것을 보이겠습니다.
다음을 주목하십시오.
size(C) = 1인 항들에서는 원소 x가 정확히 k번, 플러스 부호로 계산됩니다. size(C) = 2인 항들에서는 원소 x가 (마이너스 부호로) 정확히 C_k^2번 계산됩니다. 왜냐하면 x는 x를 포함하는 k개의 집합 중 두 집합에 대응하는 항들에서만 계산되기 때문입니다. size(C) = 3인 항들에서는 원소 x가 정확히 C_k^3번, 플러스 부호로 계산됩니다. \ldots size(C) = k인 항들에서는 원소 x가 정확히 C_k^k번, (-1)^{k-1} 부호로 계산됩니다. size(C) > k인 항들에서는 원소 x가 0번 계산됩니다. 따라서 다음과 같은 이항 계수의 합을 계산해야 합니다:
T = C_k^1 - C_k^2 + C_k^3 - \ldots + (-1)^{i-1} […]
이 합은 식 (1-x)^k를 뉴턴의 이항 정리로 전개한 것과 비교하면 가장 쉽게 계산할 수 있습니다:
(1-x)^k = C_k^0 - C_k^1 \cdot x + C_k^2 \cdot x^2[…]
x=1일 때 식 (1-x)^k는 다름 아닌 1 - T임을 알 수 있습니다. 따라서 T = 1 - (1-1)^k = 1이며, 이로써 증명이 끝났습니다.
문제 해결에서의 응용 포함-배제 원리는 그 응용 사례를 살펴보지 않고서는 제대로 이해하기 어렵습니다.
먼저 이 원리의 적용을 보여 주는 간단한 “종이 위의” 문제 세 가지를 살펴본 다음, 포함-배제 원리를 사용하지 않고는 풀기 어려운 보다 실용적인 문제들을 살펴보겠습니다.
특히 “경로 수 찾기” 문제에 주목해야 합니다. 이 문제는 포함-배제 원리가 반드시 지수 시간 해법으로 이어지는 것이 아니라 때로는 다항 시간 해법으로 이어질 수도 있음을 보여 주기 때문입니다.
순열에 관한 간단한 문제 0부터 9까지의 수로 이루어진 순열 중에서 첫 번째 원소가 1보다 크고 마지막 원소가 8보다 작은 순열은 몇 개입니까?
“나쁜” 순열, 즉 첫 번째 원소가 \le 1이거나 마지막 원소가 \ge 8인(또는 둘 다인) 순열의 개수를 세어 봅시다.
첫 번째 원소가 \le 1인 순열의 집합을 X, 마지막 원소가 \ge 8인 순열의 집합을 Y라고 합시다. 그러면 포함-배제 공식에 따라 “나쁜” 순열의 개수는 다음과 같습니다:
|X| + |Y| - |X \cap Y|.
간단한 조합 계산을 거치면 이 값은 다음과 같습니다:
2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8!
이 수를 전체 순열의 수 10!에서 빼면 답을 얻습니다.
(0,1,2)-수열에 관한 간단한 문제 숫자 0,1,2로만 이루어져 있고 각 숫자가 적어도 한 번씩 나타나는 길이 n의 수열은 몇 개입니까?
다시 여사건 문제로 넘어가겠습니다. 즉, 숫자 중 적어도 하나가 나타나지 않는 수열의 개수를 세겠습니다.
A_i (i = 0 \ldots 2)를 수 i가 나타나지 않는 수열들의 집합이라고 합시다. 그러면 포함-배제 공식에 의해 “나쁜” 수열의 개수는 다음과 같습니다:
|A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \ca[…]
각 A_i의 크기는 분명히 2^n입니다(이러한 수열에는 두 종류의 숫자만 나타날 수 있기 때문입니다). 각 쌍별 교집합 A_i \cap A_j의 크기는 1입니다(사용할 수 있는 숫자가 하나만 남기 때문입니다). 마지막으로, 세 집합 모두의 교집합의 크기는 0입니다(사용할 수 있는 숫자가 하나도 남지 않기 때문입니다).
우리가 역문제를 풀었다는 것을 떠올리면 최종 답은 다음과 같습니다:
3^n - 3 \cdot 2^n + 3 \cdot 1 - 0.
방정식의 정수 해의 개수 다음 방정식이 주어집니다:
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20,
여기서 모든 0 \le x_i \le 8입니다(여기서 i = 1 \ldots 6).
이 방정식의 해의 개수를 구해야 합니다.
먼저 x_i \le 8이라는 제약을 잊고, 이 방정식의 음이 아닌 해의 개수를 단순히 세어 봅시다. 이는 이항 계수를 이용하면 쉽게 구할 수 있습니다. 20개의 원소를 6개의 그룹으로 나누려는 것이므로, 그룹을 구분하는 5개의 “칸막이"를 25개의 자리에 배치하면 됩니다:
N_0 = C_{25}^5
이제 포함-배제 공식을 이용하여 “나쁜” 해의 개수, 즉 하나 이상의 x_i가 9보다 큰 방정식의 해의 개수를 세어 봅시다.
A_k(여기서 k = 1 \ldots 6)를 방정식의 해 가운데 x_k \ge 9이고 나머지 모든 x_i \ge 0(모든 i \ne k에 대해)인 해들의 집합이라고 합시다. 집합 A_k의 크기를 세기 위해, 이것이 본질적으로 두 문단 위에서 풀었던 것과 같은 조합 문제이며, 다만 이제는 9개의 원소가 고려 대상에서 제외되어 확실히 첫 번째 그룹에 속한다는 점에 주목합시다. 따라서 다음과 같습니다.
| A_k | = C_{16}^5
마찬가지로, 두 집합 A_k와 A_p의 교집합의 크기는 다음 수와 같습니다:
\left| A_k \cap A_p \right| = C_7^5
세 개 이상의 집합의 교집합의 크기는 모두 0입니다. 20개의 원소로는 9 이상인 변수를 세 개 이상 만들 수 없기 때문입니다.
이 모든 것을 포함-배제 공식에 결합하고, 우리가 여사건 문제를 풀었다는 점을 고려하면, 최종적으로 다음과 같은 답을 얻습니다:
C_{25}^5 - C_6^1 \cdot C_{16}^5 + C_6^2 \cdot C_7[…]
주어진 구간에서 서로소인 수의 개수 수 n과 r이 주어졌다고 합시다. 구간 [1; r]에서 n과 서로소인 수의 개수를 구해야 합니다.
바로 반대 문제로 넘어가겠습니다. 즉, 서로소가 아닌 수의 개수를 세어 봅시다.
수 n의 모든 소인수를 생각해 봅시다. 이를 p_i (i = 1 \ldots k)로 나타냅니다.
구간 [1;r]에서 p_i로 나누어떨어지는 수는 몇 개입니까? 그 개수는 다음과 같습니다.
\left\lfloor \frac{ r }{ p_i } \right\rfloor
그러나 이 수들을 단순히 합하면 잘못된 답을 얻게 됩니다. 일부 수(여러 p_i로 동시에 나누어떨어지는 수)가 여러 번 더해지기 때문입니다. 따라서 포함-배제 공식을 사용해야 합니다.
예를 들어, 2^k 시간에 모든 p_i들로 이루어진 집합의 부분집합을 열거하고, 그 곱을 계산한 다음, 포함-배제 공식에서 해당 항을 더하거나 빼면 됩니다.
서로소인 수의 개수를 세는 최종 구현은 다음과 같습니다:
int solve (int n, int r) { vector
int sum = 0;
for (int msk=1; msk<(1<<p.size()); ++msk) {
int mult = 1,
bits = 0;
for (int i=0; i<(int)p.size(); ++i)
if (msk & (1<<i)) {
++bits;
mult *= p[i];
}
int cur = r / mult;
if (bits % 2 == 1)
sum += cur;
else
sum -= cur;
}
return r - sum;
} 이 풀이의 시간 복잡도는 O (\sqrt{n})입니다.
주어진 구간에서 주어진 수들 중 적어도 하나의 배수인 수의 개수 n개의 수 a_i와 수 r이 주어집니다. 구간 [1; r]에서 a_i 중 적어도 하나의 배수인 수의 개수를 구해야 합니다.
풀이 알고리즘은 앞의 문제와 거의 같습니다. 수 a_i들에 대해 포함-배제 공식을 세웁니다. 즉, 이 공식의 각 항은 a_i 가운데 주어진 부분집합의 수들로 나누어떨어지는(다시 말해, 그 수들의 최소공배수로 나누어떨어지는) 수의 개수입니다.
따라서 이 풀이는 2^n번에 걸쳐 수의 부분집합을 순회하면서, O(n \log r)번의 연산으로 그 수들의 최소공배수를 구하고, 해당 값을 답에 더하거나 빼는 것으로 귀결됩니다.
주어진 개수의 패턴을 만족하는 문자열의 개수 n개의 패턴이 주어집니다. 패턴은 길이가 모두 같고 문자와 물음표로만 이루어진 문자열입니다. 또한 수 k가 주어집니다. 정확히 k개의 패턴을 만족하는 문자열의 개수, 또는 다른 형태의 문제에서는 적어도 k개의 패턴을 만족하는 문자열의 개수를 구해야 합니다.
먼저, 주어진 모든 패턴을 동시에 만족하는 문자열의 개수는 쉽게 셀 수 있다는 점에 주목합시다. 이를 위해서는 단순히 이 패턴들을 “교차"시키기만 하면 됩니다. 즉, 첫 번째 문자를 살펴보고(모든 패턴의 첫 번째 위치에 물음표가 있는지, 아니면 그렇지 않은지를 확인합니다. 그렇지 않다면 첫 번째 문자는 유일하게 결정됩니다), 두 번째 문자를 살펴보는 식으로 계속합니다.
이제 문제의 첫 번째 변형, 즉 찾는 문자열이 정확히 k개의 패턴을 만족해야 하는 경우를 푸는 방법을 알아봅시다.
이를 위해 크기가 k인 패턴의 특정 부분집합 X를 하나씩 골라 고정합니다. 이제 우리는 이 패턴 집합을, 그리고 오직 이 집합만을 만족하는 문자열의 개수를 세어야 합니다. 이를 위해 포함-배제 공식을 사용합시다. 집합 X의 모든 상위집합에 대해 합을 구하는데, 현재 집합에 맞는 문자열의 개수를 현재 답에 더하거나 현재 답에서 뺍니다:
ans(X) = \sum_{Y \supseteq X} (-1)^{|Y|-k} \cdot […]
여기서 f(Y)는 패턴 집합 Y에 맞는 문자열의 개수를 나타냅니다.
모든 X에 대해 ans(X)를 합하면 다음과 같이 답을 얻습니다:
ans = \sum_{X ~ : ~ |X| = k} ans(X).
그러나 이렇게 해서 우리는 O(3^k \cdot k) 정도의 시간이 걸리는 풀이를 얻었습니다.
서로 다른 ans(X)에서 합산이 종종 같은 집합 Y들에 대해 이루어진다는 점에 주목하면 풀이를 더 빠르게 만들 수 있습니다.
포함-배제 공식을 뒤집어 Y에 대해 합을 구해 봅시다. 그러면 집합 Y가 C_{|Y|}^k개의 포함-배제 공식에서 모두 같은 부호 (-1)^{|Y|-k}로 계산된다는 것을 쉽게 알 수 있습니다.
ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot[…]
이렇게 얻은 해법의 시간 복잡도는 O(2^k \cdot k)입니다.
이제 문제의 두 번째 변형으로 넘어갑시다. 이번에는 찾으려는 문자열이 적어도 k개의 패턴을 만족해야 합니다.
물론, 문제의 첫 번째 변형에 대한 풀이를 그대로 사용하여 k부터 n까지의 답을 합산할 수 있습니다. 그러나 모든 논증이 여전히 성립한다는 점을 알 수 있습니다. 다만 이 변형에서는 X에 대한 합이 크기가 정확히 k인 집합들뿐만 아니라 크기가 \ge k인 모든 집합에 걸쳐 이루어집니다.
따라서 최종 공식에서 f(Y) 앞에는 다른 계수가 붙게 됩니다. 어떤 부호가 붙은 이항 계수 하나가 아니라, 그러한 계수들의 합이 붙습니다.
(-1)^{|Y|-k} \cdot C_{|Y|}^k ~~ + ~~ (-1)^{|Y|-k-[…]
그레이엄(그레이엄, 커누스, 파타시닉. 《구체 수학》 [1998])을 들여다보면, 이항 계수에 대한 다음과 같은 잘 알려진 공식을 볼 수 있습니다:
\sum_{k=0}^m (-1)^k \cdot C_n^k = (-1)^m \cdot C_[…]
이것을 여기에 적용하면, 이 이항 계수의 합 전체가 다음과 같이 정리됨을 얻습니다:
(-1)^{|Y|-k} \cdot C_{|Y|-1}^{|Y|-k}.
따라서 이 변형 문제에 대해서도 점근적 복잡도가 O(2^k \cdot k)인 해법을 얻었습니다:
ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot[…]
경로의 수 n \times m 크기의 격자가 있고, 그중 k개의 칸은 지나갈 수 없는 벽입니다. 격자의 (1,1) 칸(왼쪽 아래 칸)에 처음에 로봇이 놓여 있습니다. 로봇은 오른쪽이나 위쪽으로만 움직일 수 있으며, 모든 장애물을 피해 최종적으로 (n,m) 칸에 도달해야 합니다. 로봇이 이렇게 이동할 수 있는 경로의 수를 구해야 합니다.
크기 n과 m은 매우 크고(예를 들어 10^9까지), 개수 k는 작다고(100 정도) 가정합니다.
풀이의 편의를 위해, 먼저 장애물을 우리가 지나갈 수 있는 순서대로 정렬합시다. 예를 들어 x 좌표 기준으로 정렬하고, x 좌표가 같으면 y 좌표 기준으로 정렬합니다.
또한 장애물이 없는 경우의 문제를 푸는 방법도 바로 익혀 둡시다. 즉, 한 칸에서 다른 칸까지 가는 방법의 수를 세는 법을 익혀 둡시다. 한 좌표 방향으로 x칸, 다른 좌표 방향으로 y칸을 이동해야 한다면, 간단한 조합론을 통해 이항 계수를 이용한 다음 공식을 얻습니다.
C_{x+y}^{x}
이제 모든 장애물을 피하면서 한 칸에서 다른 칸까지 도달하는 방법의 수를 세려면 포함-배제 공식을 사용할 수 있습니다. 적어도 하나의 장애물을 밟으면서 도달하는 방법의 수를 세어 봅시다.
이를 위해, 예를 들어 우리가 반드시 밟게 될 장애물들의 부분집합을 열거하고, 그렇게 하는 방법의 수를 센 다음(시작 칸에서 선택한 장애물 중 첫 번째 장애물까지 가는 방법의 수, 첫 번째 장애물에서 두 번째 장애물까지 가는 방법의 수 등을 단순히 모두 곱하면 됩니다), 표준 포함-배제 공식에 따라 이 수를 답에 더하거나 답에서 뺄 수 있습니다.
그러나 이것 역시 다항 시간 풀이가 아니며, 점근적 복잡도는 O (2^k k)입니다. 다항 시간 풀이를 얻는 방법을 보이겠습니다.
동적 계획법으로 풀겠습니다. 수 d[i][j]를 계산하는 방법을 알아봅시다. 이는 i번째 점에서 j번째 점까지 어떤 장애물도 밟지 않고(물론 i와 j 자체는 제외합니다) 도달하는 방법의 수입니다. 장애물에 시작 칸과 끝 칸이 추가되므로 점은 모두 k+2개입니다.
잠시 모든 장애물을 무시하고 단순히 칸 i에서 칸 j로 가는 경로의 수를 센다면, 장애물을 지나가는 몇몇 “나쁜” 경로까지 함께 세게 됩니다. 이러한 “나쁜” 경로의 수를 세는 방법을 알아봅시다. 우리가 처음으로 밟게 되는 장애물 i < t < j를 전부 시도해 봅시다. 그러면 경로의 수는 d[i][t]에 t에서 j로 가는 임의의 경로의 수를 곱한 값과 같습니다. 이를 모든 t에 대해 합하면 “나쁜” 경로의 수를 구할 수 있습니다.
이와 같이 우리는 d[i][j] 값을 O(k) 시간에 계산하는 방법을 알게 되었습니다. 따라서 전체 문제의 해법은 O(k^3)의 점근적 복잡도를 가집니다.
서로소인 네 수의 개수 n개의 수 a_1, a_2, \ldots, a_n이 주어집니다. 이 중에서 네 수를 골라, 그 네 수 전체의 최대공약수가 1이 되도록 하는 방법의 수를 구해야 합니다.
반대 문제를 풀겠습니다. 즉, “나쁜” 네 쌍의 개수, 다시 말해 모든 수가 어떤 수 d > 1로 나누어떨어지는 네 쌍의 개수를 세겠습니다.
포함-배제 공식을 이용하여, 약수 d로 나누어떨어지는(단, 더 큰 약수로도 나누어떨어질 수 있는) 네 쌍의 개수를 합산합시다:
ans = \sum_{d \ge 2} (-1)^{deg(d)-1} \cdot f(d),
여기서 deg(d)는 수 d의 소인수분해에 나타나는 소수의 개수이고, f(d)는 d로 나누어떨어지는 네 쌍의 개수입니다.
함수 f(d)를 계산하려면 d의 배수인 수의 개수를 세고, 이항 계수를 이용해 그중에서 네 수의 쌍을 고르는 방법의 수를 계산하기만 하면 됩니다.
따라서 포함-배제 공식을 이용하여 소수로 나누어떨어지는 네 수 묶음의 개수를 더하고, 그다음 두 소수의 곱으로 나누어떨어지는 네 수 묶음의 개수를 빼고, 세 소수의 곱으로 나누어떨어지는 네 수 묶음의 개수를 더하는 식으로 계속합니다.
조화 삼중쌍의 개수 수 n \le 10^6이 주어집니다. 2 \le a < b < c \le n인 수의 삼중쌍 중에서 조화 삼중쌍인 것의 개수를 세어야 합니다. 즉, 다음 조건을 만족하는 삼중쌍입니다:
{\rm gcd}(a,b) = {\rm gcd}(a,c) = {\rm gcd}(b,c) = 1이거나, {\rm gcd}(a,b) > 1, {\rm gcd}(a,c) > 1, {\rm gcd}(b,c) > 1인 경우입니다. 먼저, 곧바로 반대 문제로 넘어갑시다. 즉, 조화롭지 않은 세 수의 개수를 셉니다.
둘째로, 임의의 비조화 삼중쌍에서 정확히 두 개의 수가 삼중쌍의 한 수와는 서로소이고 삼중쌍의 다른 한 수와는 서로소가 아닌 상황에 놓인다는 점에 주목합시다.
따라서 비조화 삼중쌍의 개수는 2부터 n까지의 모든 수에 대하여, 현재 수와 서로소인 수의 개수와 서로소가 아닌 수의 개수를 곱한 값의 합과 같습니다.
이제 문제를 풀기 위해 남은 것은 구간 [2;n]의 각 수에 대해 그 수와 서로소인(또는 서로소가 아닌) 수의 개수를 세는 방법을 익히는 것뿐입니다. 이 문제는 앞에서 이미 다루었지만, 앞에서 설명한 풀이는 여기에 적합하지 않습니다. 그 풀이는 2부터 n까지의 각 수를 소인수분해한 다음, 소인수분해에 나온 소수들의 가능한 모든 곱을 전부 살펴보아야 하기 때문입니다.
따라서 구간 [2;n]의 모든 수에 대한 답을 한꺼번에 계산하는 더 빠른 풀이가 필요합니다.
이를 위해 다음과 같이 에라토스테네스의 체를 변형하여 구현할 수 있습니다:
첫째로, 구간 [2;n]에 속한 수 가운데 소인수분해에서 어떤 소수도 두 번 이상 나타나지 않는 수를 모두 찾아야 합니다. 또한 포함-배제 공식을 적용하려면 이러한 각 수의 소인수분해에 소수가 몇 개 들어 있는지 알아야 합니다. 이를 위해 각 수에 대해 소인수분해에 들어 있는 소수의 개수를 저장하는 배열 deg[]와, 각 수에 대해 모든 소수가 \le 1 거듭제곱으로 들어 있는지 여부를 true 또는 false로 저장하는 배열 good[]을 만들어야 합니다.
그 후 에라토스테네스의 체를 수행하는 동안 다음 소수를 처리할 때, 현재 수의 배수인 모든 수를 순회하며 그 수들의 deg[]를 증가시키고, 현재 소수의 제곱의 배수인 모든 수에는 good = false를 설정합니다.
둘째로, 2부터 n까지의 모든 수에 대한 답, 즉 배열 cnt[]를 계산해야 합니다. 이는 주어진 수와 서로소가 아닌 수의 개수입니다. 이를 위해 포함-배제 공식이 어떻게 작동하는지 떠올려 봅시다. 여기서 우리는 사실상 같은 공식을 구현하지만, 논리를 뒤집어서 구현합니다. 즉, 항을 하나씩 순회하면서 그 항이 어떤 수들에 대한 포함-배제 공식에 들어가는지를 살펴보는 셈입니다.
그러면 good[]=true인 수 i, 즉 포함-배제 공식에 참여하는 수가 있다고 합시다. i의 배수인 모든 수를 순회하면서, 그러한 각 수의 답 cnt[]에 \lfloor N/i \rfloor 값을 더하거나 빼야 합니다. 더할지 뺄지의 부호는 deg[i]에 따라 결정됩니다. deg[i]가 홀수이면 더하고, 그렇지 않으면 빼야 합니다.
구현:
int n; bool good[MAXN]; int deg[MAXN], cnt[MAXN];
long long solve() { memset (good, 1, sizeof good); memset (deg, 0, sizeof deg); memset (cnt, 0, sizeof cnt);
long long ans_bad = 0;
for (int i=2; i<=n; ++i) {
if (good[i]) {
if (deg[i] == 0) deg[i] = 1;
for (int j=1; i*j<=n; ++j) {
if (j > 1 && deg[i] == 1)
if (j % i == 0)
good[i*j] = false;
else
++deg[i*j];
cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);
}
}
ans_bad += (cnt[i] - 1) * 1ll * (n-1 - cnt[i]);
}
return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
} 이러한 풀이의 점근적 복잡도는 O (n \log n)입니다. 거의 모든 수 i에 대해 중첩 루프를 약 n/i번 반복하기 때문입니다.
고정점이 없는 순열의 개수 길이가 n이고 고정점이 없는 순열의 개수가 다음 수와 같음을 증명합시다:
n! - C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! - C_[…]
이는 대략 다음 수와 같습니다:
\frac{ n! }{ e }
(더욱이, 이 식을 가장 가까운 정수로 반올림하면 고정점이 없는 순열의 수와 정확히 같아집니다)
위치 k에 고정점을 갖는 길이 n인 순열의 집합을 A_k로 나타냅시다 (1 \le k \le n).
이제 포함-배제 공식을 이용하여 고정점이 적어도 하나 있는 순열의 개수를 세어 봅시다. 이를 위해서는 교집합 A_i의 크기를 구할 수 있어야 하며, 그 크기는 다음과 같습니다:
\left| A_p \right| = (n-1)! ~, \left| A_p \cap A_q \right| = (n-2)! ~, \left| A_p \cap A_q \cap A_r \right| = (n-3)! ~, \ldots ~,
고정점의 개수가 x라는 것을 알면 그로써 순열의 x개 원소의 위치를 알게 되고, 나머지 (n-x)개의 원소는 어디에든 놓일 수 있기 때문입니다.
이것을 포함-배제 공식에 대입하고, n개의 원소로 이루어진 집합에서 크기가 x인 부분집합을 고르는 방법의 수가 C_n^x라는 점을 고려하면, 고정점을 적어도 하나 가진 순열의 개수에 대한 공식을 얻습니다:
C_n^1 \cdot (n-1)! - C_n^2 \cdot (n-2)! + C_n^3 […]
그러면 고정점이 없는 순열의 개수는 다음과 같습니다:
n! - C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! - C_[…]
이 식을 정리하면, 고정점이 없는 순열의 개수에 대한 정확한 식과 근사식을 얻습니다:
n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac[…]
(괄호 안의 합은 e^{-1}의 테일러 급수 전개의 처음 n+1개 항이기 때문입니다)
끝으로, 순열의 모든 원소가 아니라 처음 m개의 원소 중에 고정점이 없어야 하는 문제도 (방금 우리가 푼 것처럼 모든 원소에 대한 경우가 아니라) 같은 방식으로 풀 수 있다는 점을 짚어 둘 만합니다. 공식은 위에서 제시한 정확한 공식과 같은 형태가 되며, 다만 그 안의 합이 n이 아니라 k까지 진행됩니다.