포함-배제 원리¶

포함-배제 원리는 집합의 크기나 복잡한 사건의 확률을 계산하는 중요한 조합론적 방법입니다. 이 원리는 개별 집합들의 크기와 그 합집합의 크기를 연결합니다.

명제¶

말로 표현한 공식¶

포함-배제 원리는 다음과 같이 표현할 수 있습니다:

여러 집합의 합집합의 크기를 계산하려면, 먼저 각 집합의 크기를 따로따로 더한 다음, 집합들의 모든 쌍별 교집합의 크기를 빼고, 이어서 집합 세 개씩의 교집합의 크기를 다시 더하고, 집합 네 개씩의 교집합의 크기를 빼는 식으로 모든 집합의 교집합까지 계속해야 합니다.

집합을 이용한 공식화¶

위의 정의는 수학적으로 다음과 같이 표현할 수 있습니다:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n|A_i| - \sum_{1\leq i<j\leq n} |A_i \cap A_j| + \sum _{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} | A_1 \cap \cdots \cap A_n |$$

더 간결하게 쓰면 다음과 같습니다:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

벤 다이어그램을 이용한 공식화¶

다이어그램에 세 집합 $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) - S(A \cap B) - S(A \cap C) - S(B \cap C) + S(A \cap B \cap C)$$

이는 $n$개의 집합에 대해서도 일반화할 수 있습니다.

확률론을 이용한 공식화¶

$A_i$ $(i = 1,2...n)$가 사건이고 ${\cal P}(A_i)$가 사건 $A_i$가 일어날 확률이라면, 이 사건들의 합사건의 확률(즉, 사건들 중 적어도 하나가 일어날 확률)은 다음과 같습니다:

$$\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n A_i \right) &=& \sum_{i=1}^n{\cal P}(A_i)\ - \sum_{1\leq i<j\leq n} {\cal P}(A_i \cap A_j)\ + \\ &+& \sum _{1\leq i<j<k\leq n}{\cal P}(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n-1} {\cal P}( A_1 \cap \cdots \cap A_n ) \end{eqnarray}$$

더 간결하게 쓰면 다음과 같습니다:

$${\cal P} \left(\bigcup_{i=1}^n A_i \right) = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}\ {\cal P}{\Biggl (}\bigcap_{j\in J}A_{j}{\Biggr )}$$

증명¶

증명에는 집합론을 이용한 수학적 공식화를 사용하는 것이 편리합니다:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

집합 $A_i$ 중 적어도 하나에 포함된 모든 원소가 공식에서 정확히 한 번만 세어진다는 것을 증명하고자 합니다(어떤 집합 $A_i$에도 속하지 않는 원소는 공식의 우변에서 전혀 고려되지 않는다는 점에 유의하십시오).

$k \geq 1$개의 집합 $A_i$에 속하는 원소 $x$를 생각해 봅시다. 이 원소가 공식에서 정확히 한 번만 세어진다는 것을 보이겠습니다. 다음 사항에 유의하십시오:

$|J| = 1$인 항들에서 원소 $x$는 $+\ k$번 세어집니다;
$|J| = 2$인 항들에서 원소 $x$는 $-\ \binom{k}{2}$번 세어집니다. $x$를 포함하는 $k$개의 집합 중 두 개를 포함하는 항들에서 세어지기 때문입니다;
$|J| = 3$인 항들에서 원소 $x$는 $+\ \binom{k}{3}$번 세어집니다;
$\cdots$
$|J| = k$인 항들에서 원소 $x$는 $(-1)^{k-1}\cdot \binom{k}{k}$번 세어집니다;
$|J| \gt k$인 항들에서 원소 $x$는 0번 세어집니다;

이로부터 다음과 같은 이항 계수의 합을 얻습니다:

$$ T = \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots + (-1)^{i-1}\cdot \binom{k}{i} + \cdots + (-1)^{k-1}\cdot \binom{k}{k}$$

이 식은 $(1 - x)^k$의 이항 전개와 매우 비슷합니다:

$$ (1 - x)^k = \binom{k}{0} - \binom{k}{1} \cdot x + \binom{k}{2} \cdot x^2 - \binom{k}{3} \cdot x^3 + \cdots + (-1)^k\cdot \binom{k}{k} \cdot x^k $$

$x = 1$일 때 $(1 - x)^k$는 $T$와 매우 비슷해 보입니다. 하지만 이 식에는 $\binom{k}{0} = 1$이 추가로 들어 있고, $-1$이 곱해져 있습니다. 따라서 $(1 - 1)^k = 1 - T$를 얻습니다. 그러므로 $T = 1 - (1 - 1)^k = 1$이며, 이것이 증명하려던 내용입니다. 해당 원소는 정확히 한 번만 세어집니다.

정확히 $r$개의 집합에 속하는 원소의 개수를 구하기 위한 일반화¶

포함-배제 원리는 어느 집합에도 속하지 않는 원소의 개수를 구하는 형태로 다시 쓸 수 있습니다:

$$\left|\bigcap_{i=1}^n \overline{A_i}\right|=\sum_{m=0}^n (-1)^m \sum_{|X|=m} \left|\bigcap_{i\in X} A_{i}\right|$$

이를 일반화하여 정확히 $r$개의 집합에 속하는 원소의 개수를 구하는 방법을 살펴봅시다:

$$\left|\bigcup_{|B|=r}\left[\bigcap_{i \in B} A_i \cap \bigcap_{j \not\in B} \overline{A_j}\right]\right|=\sum_{m=r}^n (-1)^{m-r}\dbinom{m}{r} \sum_{|X|=m} \left|\bigcap_{i \in X} A_{i}\right|$$

이 공식을 증명하기 위해 특정한 $B$ 하나를 생각해 봅시다. 기본 포함-배제 원리에 따라 이에 대해 다음과 같이 말할 수 있습니다:

$$\left|\bigcap_{i \in B} A_i \cap \bigcap_{j \not \in B} \overline{A_j}\right|=\sum_{m=r}^{n} (-1)^{m-r} \sum_{\substack{|X|=m \newline B \subset X}}\left|\bigcap_{i\in X} A_{i}\right|$$

서로 다른 $B$에 대해 좌변의 집합들은 서로 겹치지 않으므로, 이들을 그대로 더할 수 있습니다. 또한 임의의 집합 $X$는 등장할 때마다 항상 계수 $(-1)^{m-r}$을 가지며, 정확히 $\dbinom{m}{r}$개의 집합 $B$에 대해 등장한다는 점에 유의해야 합니다.

문제 풀이에서의 활용¶

포함-배제 원리는 그 활용 예를 살펴보지 않고서는 이해하기 어렵습니다.

먼저 이 원리의 활용을 보여 주는 가장 간단한 세 가지 과제를 "종이 위에서" 살펴본 다음, 포함-배제 원리 없이는 풀기 어려운 좀 더 실용적인 문제들을 다루겠습니다.

"경우의 수를 구하는" 과제는 주목할 만합니다. 이러한 과제는 반드시 지수 시간 풀이가 아니라 때로는 다항 시간 풀이로 이어지기 때문입니다.

순열에 관한 간단한 과제¶

과제: $0$부터 $9$까지의 수로 이루어진 순열 중에서 첫 번째 원소가 $1$보다 크고 마지막 원소가 $8$보다 작은 순열이 몇 개인지 세십시오.

"나쁜" 순열, 즉 첫 번째 원소가 $\leq 1$이거나 마지막 원소가 $\geq 8$인(또는 둘 다인) 순열의 개수를 세어 봅시다.

첫 번째 원소가 $\leq 1$인 순열의 집합을 $X$로, 마지막 원소가 $\geq 8$인 순열의 집합을 $Y$로 나타내겠습니다. 그러면 포함-배제 공식에 따라 "나쁜" 순열의 개수는 다음과 같습니다:

$$ |X \cup 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$인 수열 중에서 각 수가 적어도 한 번 등장하는 수열이 몇 개인지 세십시오.

이번에도 역문제로 바꾸어, 즉 수들 중 적어도 하나를 포함하지 않는 수열의 개수를 구해 봅시다.

숫자 $i$가 등장하지 않는 수열의 집합을 $A_i (i = 0,1,2)$로 나타냅시다. "나쁜" 수열의 개수에 대한 포함-배제 공식은 다음과 같습니다:

$$ |A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2| $$

각 수열은 숫자 두 개만 포함할 수 있으므로, 각 $A_i$의 크기는 $2^n$입니다.
수열을 만드는 데 쓸 수 있는 숫자가 하나뿐이므로, 각 쌍의 교집합 $A_i \cap A_j$의 크기는 $1$입니다.
수열을 만드는 데 쓸 수 있는 숫자가 없으므로, 세 집합 모두의 교집합의 크기는 $0$입니다.

여사건 문제를 풀었으므로, 전체 $3^n$개의 수열에서 이를 뺍니다:

$$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,2,\ldots 6)$입니다.

과제: 이 방정식의 해의 개수를 세십시오.

잠시 $x_i$에 대한 제약은 잊고, 이 방정식의 음이 아닌 해의 개수만 세어 봅시다. 이는 별과 막대를 이용하면 쉽게 구할 수 있습니다: $20$개의 단위로 이루어진 수열을 $6$개의 그룹으로 나누려는 것이며, 이는 $5$개의 막대와 $20$개의 별을 배열하는 것과 같습니다:

$$N_0 = \binom{25}{5}$$

이제 포함-배제 원리를 이용해 "나쁜" 해의 개수를 계산하겠습니다. "나쁜" 해란 하나 이상의 $x_i$가 $9$ 이상인 해를 말합니다.

$x_k \ge 9$이고 나머지 모든 $x_i \ge 0 ~ (i \ne k)$인(이들은 $\ge 9$일 수도 있고 아닐 수도 있습니다) 해의 집합을 $A_k ~ (k = 1,2\ldots 6)$로 나타냅시다. $A_k$의 크기를 계산하려면, 이것이 본질적으로 두 문단 위에서 푼 것과 같은 조합 문제이지만, 이제 단위 중 $9$개가 슬롯에서 제외되어 반드시 첫 번째 그룹에 속한다는 점에 주목하십시오. 따라서:

$$ | A_k | = \binom{16}{5} $$

마찬가지로, 두 집합 $A_k$와 $A_p$($k \ne p$)의 교집합의 크기는 다음과 같습니다:

$$ \left| A_k \cap A_p \right| = \binom{7}{5}$$

세 집합의 교집합의 크기는 모두 0입니다. $20$개의 단위로는 세 개 이상의 변수가 $9$ 이상이 되기에 충분하지 않기 때문입니다.

이 모든 것을 포함-배제 공식으로 결합하고, 여사건 문제를 풀었다는 점을 고려하면, 최종적으로 다음 답을 얻습니다:

$$\binom{25}{5} - \left(\binom{6}{1} \cdot \binom{16}{5} - \binom{6}{2} \cdot \binom{7}{5}\right) $$

이는 $0 \le x_i \le b$라는 제약 아래 합이 $s$가 되는 $d$개의 수로 쉽게 일반화됩니다:

$$\sum_{i=0}^d (-1)^i \binom{d}{i} \binom{s+d-1-(b+1)i}{d-1}$$

위에서와 마찬가지로, 위쪽 인덱스가 음수인 이항 계수는 0으로 취급합니다.

이 문제는 동적 계획법이나 생성 함수로도 풀 수 있다는 점에 유의하십시오. 포함-배제를 이용한 답은 $O(d)$ 시간에 계산되는 반면(이항 계수 같은 수학 연산이 상수 시간이라고 가정할 때), 단순한 DP 접근법은 $O(ds)$ 시간이 걸립니다.

주어진 구간에서 서로소인 수의 개수¶

과제: 두 수 $n$과 $r$이 주어질 때, 구간 $[1;r]$에서 n과 서로소인(최대공약수가 $1$인) 정수의 개수를 세십시오.

여사건 문제를 풀어 봅시다. 즉, $n$과 서로소가 아닌 수의 개수를 계산합니다.

$n$의 소인수를 $p_i (i = 1\cdots k)$로 나타내겠습니다.

구간 $[1;r]$에서 $p_i$로 나누어떨어지는 수는 몇 개입니까? 이 질문에 대한 답은 다음과 같습니다:

$$ \left\lfloor \frac{ r }{ p_i } \right\rfloor $$

그러나 이 수들을 단순히 더하면, 일부 수(여러 $p_i$를 인수로 공유하는 수)는 여러 번 합산됩니다. 따라서 포함-배제 원리를 사용해야 합니다.

$p_i$들의 모든 $2^k$개 부분집합을 순회하면서 각 부분집합의 곱을 계산하고, 그 곱의 배수의 개수를 더하거나 뺍니다.

다음은 C++ 구현입니다:

int solve (int n, int r) {
    vector<int> p;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    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$의 주어진 부분집합으로 나누어떨어지는(다시 말해, 그 수들의 최소공배수로 나누어떨어지는) 수의 개수입니다.

따라서 이제 정수 $a_i$의 $2^n$개 부분집합을 모두 순회하면서 $O(n \log r)$번의 연산으로 각 부분집합의 최소공배수를 구하고, 구간 안에 있는 그 배수의 개수를 더하거나 뺍니다. 점근 복잡도는 $O (2^n\cdot n\cdot \log r)$입니다.

주어진 패턴을 만족하는 문자열의 개수¶

문자($a...z$) 또는 물음표로만 이루어진 같은 길이의 문자열 패턴 $n$개를 생각해 봅시다. 수 $k$도 주어집니다. 문자열이 패턴과 길이가 같고, 각 위치에서 대응하는 문자가 같거나 패턴의 문자가 물음표이면 그 문자열은 패턴과 일치합니다. 과제는 정확히 $k$개의 패턴과 일치하는 문자열의 개수(첫 번째 문제)와 적어도 $k$개의 패턴과 일치하는 문자열의 개수(두 번째 문제)를 세는 것입니다.

먼저 지정된 모든 패턴을 동시에 만족하는 문자열의 개수는 쉽게 셀 수 있다는 점에 주목하십시오. 이를 위해서는 패턴들을 단순히 "교차"하면 됩니다. 위치("슬롯")를 순회하면서 모든 패턴에서 해당 위치를 살펴봅니다. 모든 패턴의 이 위치가 물음표라면, 그 문자는 $a$부터 $z$까지 어떤 문자든 될 수 있습니다. 그렇지 않으면, 이 위치의 문자는 물음표를 포함하지 않는 패턴들에 의해 유일하게 정해집니다.

이제 문제의 첫 번째 버전, 즉 문자열이 정확히 $k$개의 패턴을 만족해야 하는 경우를 푸는 방법을 알아봅시다.

이를 풀기 위해, 패턴 집합에서 $k$개의 패턴으로 이루어진 특정 부분집합 $X$를 순회하며 고정합니다. 그러면 이 패턴 집합을 만족하면서 오직 이 집합과만 일치하는, 즉 다른 어떤 패턴과도 일치하지 않는 문자열의 개수를 세야 합니다. 포함-배제 원리를 약간 다른 방식으로 사용하겠습니다. 모든 상위 집합 $Y$(원래 문자열 집합의 부분집합 중 $X$를 포함하는 것)에 대해 합을 구하며, 문자열의 개수를 현재 답에 더하거나 뺍니다:

$$ ans(X) = \sum_{Y \supseteq X} (-1)^{|Y|-k} \cdot f(Y) $$

여기서 $f(Y)$는 $Y$와 일치하는(적어도 $Y$와 일치하는) 문자열의 개수입니다.

(이 부분을 이해하기 어렵다면 벤 다이어그램을 그려 보십시오.)

모든 $ans(X)$를 합하면 최종 답을 얻습니다:

$$ ans = \sum_{X ~ : ~ |X| = k} ans(X) $$

$X$를 고르는 방법은 $\binom{n}{k}$가지이고, 각각은 $2^{n-k}$개의 상위 집합을 가집니다. 집합 하나를 처리하는 데 $O(n)$이 든다면, 이 직접적인 방법은 $O\left(\binom{n}{k} 2^{n-k} n\right)$ 시간이 걸립니다. 이를 개선하려면, 서로 다른 $ans(X)$ 계산이 $Y$ 집합을 매우 자주 공유한다는 점에 주목하십시오.

포함-배제 공식을 뒤집어 $Y$ 집합 기준으로 합을 구하겠습니다. 이제 같은 집합 $Y$가 $\binom{|Y|}{k}$개 집합의 $ans(X)$ 계산에서 같은 부호 $(-1)^{|Y| - k}$로 고려된다는 것이 분명해집니다.

$$ ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|}{k} \cdot f(Y) $$

이제 풀이의 점근 복잡도는 $O(2^n \cdot n)$입니다.

이제 문제의 두 번째 버전을 풀겠습니다. 적어도 $k$개의 패턴과 일치하는 문자열의 개수를 구합니다.

물론 문제의 첫 번째 버전의 풀이를 그대로 사용하여 크기가 $k$보다 큰 집합들의 답을 더할 수도 있습니다. 그러나 이 문제에서 크기가 $|Y|$인 집합 $Y$는 $Y$에 포함되는 크기 $\ge k$의 모든 집합에 대한 공식에서 고려된다는 것을 알 수 있습니다. 따라서 식에서 $f(Y)$에 곱해지는 부분을 다음과 같이 쓸 수 있습니다:

$$ (-1)^{|Y|-k} \cdot \binom{|Y|}{k} + (-1)^{|Y|-k-1} \cdot \binom{|Y|}{k+1} + (-1)^{|Y|-k-2} \cdot \binom{|Y|}{k+2} + \cdots + (-1)^{|Y|-|Y|} \cdot \binom{|Y|}{|Y|} $$

Graham의 책(Graham, Knuth, Patashnik. "Concrete mathematics" [1998] )을 보면, 이항 계수에 대해 잘 알려진 공식이 있습니다:

$$ \sum_{k=0}^m (-1)^k \cdot \binom{n}{k} = (-1)^m \cdot \binom{n-1}{m} $$

이를 여기에 적용하면, 이항 계수의 전체 합이 최소화됨을 알 수 있습니다:

$$ (-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k} $$

따라서 이 문제에 대해서도 $O(2^n \cdot n)$의 점근적 복잡도를 갖는 풀이를 얻었습니다:

$$ ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k} \cdot f(Y) $$

한 칸에서 다른 칸으로 가는 방법의 수¶

$n \times m$ 크기의 필드가 있으며, 그중 $k$개의 칸은 지나갈 수 없는 벽입니다. 로봇은 처음에 $(1,1)$ 칸(왼쪽 아래)에 있습니다. 로봇은 오른쪽이나 위쪽으로만 이동할 수 있으며, 모든 장애물을 피해 최종적으로 $(n,m)$ 칸에 도달해야 합니다. 로봇이 이를 수행할 수 있는 방법의 수를 세어야 합니다.

크기 $n$과 $m$은 매우 크고(예를 들어 $10^9$), 수 $k$는 작다고(약 $100$) 가정합니다.

우선 장애물을 좌표 $x$ 기준으로 정렬하고, 같은 경우에는 좌표 $y$ 기준으로 정렬합니다.

또한 장애물이 없는 문제를 푸는 방법, 즉 한 칸에서 다른 칸으로 가는 방법의 수를 세는 방법을 익혀 둡니다. 한 축으로는 $x$칸을, 다른 축으로는 $y$칸을 지나가야 합니다. 간단한 조합론으로부터 이항 계수를 이용한 공식을 얻습니다:

$$\binom{x+y}{x}$$

이제 모든 장애물을 피해 한 칸에서 다른 칸으로 가는 방법의 수를 세려면, 포함-배제를 사용하여 역문제를 풀 수 있습니다. 즉, 장애물의 어떤 부분집합을 밟으며 보드를 지나가는 방법의 수를 셉니다(그리고 이를 전체 방법의 수에서 뺍니다).

우리가 밟을 장애물들의 부분집합을 순회할 때, 그렇게 하는 방법의 수를 세려면 시작 칸에서 선택된 장애물 중 첫 번째까지, 첫 번째 장애물에서 두 번째까지, 그리고 이런 식으로 이어지는 모든 경로의 수를 단순히 곱하면 됩니다. 그런 다음 표준 포함-배제 공식에 따라 이 수를 답에 더하거나 답에서 뺍니다.

그러나 이 역시 복잡도가 $O(2^k \cdot k)$로 다항 시간이 아닙니다.

다항 시간 풀이는 다음과 같습니다:

동적 계획법을 사용하겠습니다. 편의를 위해 장애물 배열의 맨 앞에 (1,1)을, 맨 끝에 (n,m)을 넣습니다. 수 $d[i]$를 계산합시다. 이는 시작점(인덱스 $0$)에서 인덱스 $i$까지 다른 장애물을 밟지 않고(물론 $i$는 제외) 가는 방법의 수입니다. 이 수를 모든 장애물 칸과 도착 칸에 대해 계산하겠습니다.

잠시 장애물을 잊고 칸 $0$에서 $i$까지의 경로의 수만 세어 봅시다. 장애물을 지나는 "나쁜" 경로들을 고려하여, $0$에서 $i$까지 가는 전체 방법의 수에서 이를 빼야 합니다.

$0$과 $i$ 사이에 있으며 밟을 수 있는 장애물 $t$($0 < t < i$)를 고려할 때, $0$에서 $i$까지 $t$를 지나는 경로 중 $t$가 시작점과 $i$ 사이의 첫 번째 장애물인 경로의 수를 살펴봅니다. 이는 $d[t]$에 $t$에서 $i$까지의 임의의 경로의 수를 곱한 값으로 계산할 수 있습니다. $0$과 $i$ 사이의 모든 $t$에 대해 이를 합하여 "나쁜" 방법의 수를 셀 수 있습니다.

$O(k)$개의 장애물 각각에 대해 $d[i]$를 $O(k)$에 계산할 수 있으므로, 이 풀이의 복잡도는 $O(k^2)$입니다.

서로소인 네 수 묶음의 개수¶

$n$개의 수 $a_1, a_2, \ldots, a_n$이 주어집니다. 네 개의 수를 골라 그 네 수 전체의 최대공약수가 1이 되도록 하는 방법의 수를 세어야 합니다.

역문제를 풀겠습니다. 즉, "나쁜" 네 수 묶음, 다시 말해 모든 수가 어떤 수 $d > 1$로 나누어떨어지는 네 수 묶음의 개수를 계산합니다.

제곱 인수가 없는 약수 $d > 1$, 즉 서로 다른 소수들의 곱에 대해 합을 구하면서 포함-배제 원리를 사용하겠습니다. 제곱 인수가 있는 약수는 소수 나누어떨어짐 조건들의 새로운 교집합에 대응하지 않으므로 별도로 포함해서는 안 됩니다.

$$ans = \sum_{\substack{d \ge 2 \\ d\text{ square-free}}} (-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$입니다.

먼저, 곧바로 역문제로 넘어갑니다. 즉, 조화롭지 않은 삼중쌍의 개수를 셉니다.

둘째로, 조화롭지 않은 삼중쌍은 모두 서로소인 한 쌍과, 그 쌍 중 적어도 하나와 서로소가 아닌 세 번째 수로 이루어져 있다는 점에 주목하십시오.

따라서 $i$를 포함하는 조화롭지 않은 삼중쌍의 개수는 $2$부터 $n$까지의 정수 중 $i$와 서로소인 정수의 개수에 $i$와 서로소가 아닌 정수의 개수를 곱한 값과 같습니다.

$gcd(a,b) = 1 \wedge gcd(a,c) > 1 \wedge gcd(b,c) > 1$이거나

$gcd(a,b) = 1 \wedge gcd(a,c) = 1 \wedge gcd(b,c) > 1$입니다.

이 두 경우 모두 두 번씩 세어집니다. 첫 번째 경우는 $i = a$일 때와 $i = b$일 때 세어집니다. 두 번째 경우는 $i = b$일 때와 $i = c$일 때 세어집니다. 따라서 조화롭지 않은 삼중쌍의 개수를 구하려면 $2$부터 $n$까지의 모든 $i$에 대해 이 값을 더한 뒤 $2$로 나눕니다.

이제 남은 것은 구간 $[2;n]$에서 $i$와 서로소인 수의 개수를 세는 방법을 익히는 것뿐입니다. 이 문제는 이미 언급한 적이 있지만, 위의 풀이는 여기에 적합하지 않습니다. $2$부터 $n$까지의 각 정수를 소인수분해한 다음, 그 소수들의 모든 부분집합을 순회해야 하기 때문입니다.

에라토스테네스의 체를 다음과 같이 변형하면 더 빠른 풀이가 가능합니다.

먼저, 구간 $[2;n]$에 있는 수 중 소인수분해에 같은 소인수가 두 번 이상 포함되지 않는 수를 모두 찾습니다. 또한 이러한 수들에 대해 소인수가 몇 개 포함되어 있는지도 알아야 합니다.
- 이를 위해 $i$의 소인수분해에 포함된 소수의 개수를 저장하는 배열 $deg[i]$와, $i$가 각 소인수를 최대 한 번만 포함하는지($good[i] = 1$) 아닌지($good[i] = 0$)를 표시하는 배열 $good[i]$를 관리합니다. $2$부터 $n$까지 순회하다가 $deg$ 값이 $0$인 수에 도달하면, 그 수는 소수이며 그 $deg$ 값은 $1$입니다.
- 에라토스테네스의 체를 수행하는 동안 $i$를 $2$부터 $n$까지 순회합니다. 소수를 처리할 때는 그 소수의 모든 배수를 순회하며 그 배수들의 $deg[]$ 값을 증가시킵니다. 이 배수 중 하나가 $i$의 제곱의 배수라면, $good$을 false로 설정할 수 있습니다.
둘째로, $2$부터 $n$까지의 모든 $i$에 대해 답, 즉 $i$와 서로소가 아닌 정수의 개수인 배열 $cnt[]$를 계산해야 합니다.
- 이를 위해 포함-배제 공식이 어떻게 작동하는지 떠올려 보십시오. 실제로 여기서는 같은 개념을 반대 방향의 논리로 구현합니다. 즉, 하나의 성분(소인수분해에 나타나는 소수들의 곱)을 순회하면서, 그 성분의 각 배수에 대한 포함-배제 공식에 해당 항을 더하거나 뺍니다.
- 그러면 $good[i] = true$인 수 $i$, 즉 포함-배제 공식에 관여하는 수를 처리하고 있다고 합시다. $i$의 배수인 모든 수를 순회하면서 그 수들의 $cnt[]$에 $\lfloor n/i \rfloor$를 더하거나 빼십시오(부호는 $deg[i]$에 따라 결정됩니다. $deg[i]$가 홀수이면 더하고, 그렇지 않으면 뺍니다).

다음은 C++ 구현입니다.

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;
}

$n$ 이하의 거의 모든 수에 대해 중첩 루프에서 $n/i$번의 반복을 수행하므로, 이 풀이의 점근적 복잡도는 $O(n \log n)$입니다.

고정점이 없는 순열(교란순열)의 개수¶

고정점이 없는(즉, 어떤 수 $i$도 $i$번째 위치에 있지 않은, 교란순열이라고도 하는) 길이 $n$인 순열의 개수가 다음 수와 같음을 증명하십시오:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)! $$

그리고 근사적으로 다음과 같습니다:

$$ \frac{ n! }{ e } $$

(이 식을 가장 가까운 정수로 반올림하면 고정점이 없는 순열의 개수와 정확히 일치합니다)

위치 $k$($1 \le k \le n$)에 고정점이 있는(즉, 원소 $k$가 위치 $k$에 있는) 길이 $n$인 순열의 집합을 $A_k$라 합시다.

이제 포함-배제 공식을 사용하여 고정점이 적어도 하나 있는 순열의 개수를 셉니다. 이를 위해서는 다음과 같이 집합 $A_i$들의 교집합의 크기를 세는 법을 알아야 합니다:

$$\begin{eqnarray} \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)!\ , \\ \cdots , \end{eqnarray}$$

고정점의 개수가 $x$임을 알면 순열에서 $x$개 원소의 위치를 알 수 있고, 나머지 $(n-x)$개의 원소는 어디에나 놓일 수 있기 때문입니다.

이를 포함-배제 공식에 대입하고, $n$개의 원소로 이루어진 집합에서 크기 $x$인 부분집합을 고르는 방법의 수가 $\binom{n}{x}$라는 점을 이용하면, 고정점이 적어도 하나 있는 순열의 개수에 대한 공식을 얻습니다:

$$\binom{n}{1} \cdot (n-1)! - \binom{n}{2} \cdot (n-2)! + \binom{n}{3} \cdot (n-3)! - \cdots \pm \binom{n}{n} \cdot (n-n)! $$

그러면 고정점이 없는 순열의 개수는 다음과 같습니다:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)! $$

이 식을 정리하면 고정점이 없는 순열의 개수에 대한 정확한 식과 근사식을 얻습니다:

$$ n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right ) \approx \frac{n!}{e} $$

(괄호 안의 합은 $e^{-1}$의 테일러 급수 전개에서 처음 $n+1$개의 항이기 때문입니다)

비슷한 문제도 이 방법으로 풀 수 있다는 점을 짚어 둘 만합니다. (방금 푼 것처럼 전체 원소가 아니라) 순열의 처음 $m$개 원소 중에 고정점이 없어야 하는 경우입니다. 이때 얻는 공식은 위에서 제시한 정확한 공식과 같지만, 합이 $n$이 아니라 $m$까지만 이어집니다.

연습 문제¶

포함-배제 원리를 사용하여 풀 수 있는 문제 목록입니다: