Принцип включення-виключення

Принцип включення-виключення — це важливий комбінаторний спосіб обчислити розмір множини або ймовірність складних подій. Він пов'язує розміри окремих множин із розміром їхнього об'єднання.

Коли підходить цей алгоритм?

• Чи треба порахувати об'єкти, що задовольняють хоча б одну (або жодну) з умов, причому умови перетинаються й пряме сумування дає переоблік?
• Чи легко рахувати перетини умов (скільки об'єктів задовольняє фіксований набір умов одночасно), хоча об'єднання — важко?
• Чи кількість умов $n$ невелика (приблизно $n \lesssim 20$), щоб перебрати всі $2^n$ підмножин? (якщо умов незалежні підрахунки без перетинів → Біноміальні коефіцієнти)

Формулювання

Словесне формулювання

Принцип включення-виключення можна сформулювати так:

Щоб обчислити розмір об'єднання кількох множин, треба підсумувати розміри цих множин окремо, потім відняти розміри всіх попарних перетинів множин, далі додати назад розмір перетинів трійок множин, відняти розмір четвірок множин, і так далі, аж до перетину всіх множин.

Формулювання мовою теорії множин

Наведене вище означення можна записати математично так:

$$\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{align} {\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{align}$$

А у більш компактному вигляді:

$${\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$, ніколи не враховуються у правій частині формули).

Розглянемо елемент $x$, який зустрічається у $k \geq 1$ множинах $A_i$. Ми покажемо, що його враховано рівно один раз. Зауважимо, що:

• у доданках, де $|J| = 1$, елемент $x$ буде враховано $+\ k$ разів;
• у доданках, де $|J| = 2$, елемент $x$ буде враховано $-\ \binom{k}{2}$ разів — оскільки він враховується в тих доданках, що включають дві з $k$ множин, які містять $x$;
• у доданках, де $|J| = 3$, елемент $x$ буде враховано $+\ \binom{k}{3}$ разів;
• $\cdots$
• у доданках, де $|J| = k$, елемент $x$ буде враховано $(-1)^{k-1}\cdot \binom{k}{k}$ разів;
• у доданках, де $|J| \gt k$, елемент $x$ буде враховано нуль разів;

Це приводить нас до такої суми біноміальних коефіцієнтів:

$$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$.

Позначимо через $X$ множину перестановок, у яких перший елемент $\leq 1$, а через $Y$ — множину перестановок, у яких останній елемент $\geq 8$. Тоді кількість «поганих» перестановок за формулою включення-виключення дорівнюватиме:

$$|X \cup Y| = |X| + |Y| - |X \cap Y|$$

Після простого комбінаторного обчислення отримаємо:

$$2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8!$$

Залишається лише відняти це число від загальної кількості $10!$, щоб отримати кількість «хороших» перестановок.

Проста задача про послідовності з (0, 1, 2)

Задача: підрахувати, скільки існує послідовностей довжини $n$, які складаються лише з чисел $0,1,2$, таких, що кожне число зустрічається хоча б один раз.

Знову звернімося до оберненої задачі, тобто обчислимо кількість послідовностей, які не містять хоча б одного з чисел.

Позначимо через $A_i (i = 0,1,2)$ множину послідовностей, у яких цифра $i$ не зустрічається. Формула включення-виключення для кількості «поганих» послідовностей буде такою:

$$|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$.

Позначимо через $A_k ~ (k = 1,2\ldots 6)$ множину розв'язків, де $x_k \ge 9$, а всі інші $x_i \ge 0 ~ (i \ne k)$ (вони можуть бути $\ge 9$ або ні). Щоб обчислити розмір $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}$$

Розмір кожного перетину трьох множин дорівнює нулю, оскільки $20$ одиниць не вистачить для трьох або більше змінних, більших або рівних $9$.

Об'єднавши все це у формулу включення-виключення і враховуючи, що ми розв'язали обернену задачу, остаточно отримуємо відповідь:

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

Це легко узагальнюється на $d$ чисел, що дають у сумі $s$, з обмеженням $0 \le x_i \le b$:

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

Як і вище, ми вважаємо біноміальні коефіцієнти з від'ємним верхнім індексом нульовими.

Зауважимо, що цю задачу можна було б розв'язати також динамічним програмуванням або твірними функціями. Відповідь за принципом включення-виключення обчислюється за $O(d)$ часу (припускаючи, що математичні операції на кшталт біноміального коефіцієнта виконуються за сталий час), тоді як простий підхід із ДП потребував би $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$ серед своїх множників). Тому необхідно скористатися принципом включення-виключення.

Ми переберемо всі $2^k$ підмножин чисел $p_i$, обчислимо їхній добуток і додамо або віднімемо кількість кратних цього добутку.

Ось реалізація:

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

Python

def solve(n: int, r: int) -> int:
    # Знаходимо різні прості множники числа n
    p = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            p.append(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        p.append(n)

    total = 0
    # Перебираємо всі непорожні підмножини множників
    for msk in range(1, 1 << len(p)):
        mult = 1
        bits = 0
        for i in range(len(p)):
            if msk & (1 << i):
                bits += 1
                mult *= p[i]

        cur = r // mult
        # Непарна кількість множників — додаємо, парна — віднімаємо
        if bits % 2 == 1:
            total += cur
        else:
            total -= cur

    return r - total

TypeScript

function solve(n: number, r: number): number {
    // Знаходимо різні прості множники числа n
    const p: number[] = [];
    for (let i = 2; i * i <= n; ++i) {
        if (n % i === 0) {
            p.push(i);
            while (n % i === 0) {
                n = Math.floor(n / i);
            }
        }
    }
    if (n > 1) {
        p.push(n);
    }

    let sum = 0;
    // Перебираємо всі непорожні підмножини множників
    for (let msk = 1; msk < (1 << p.length); ++msk) {
        let mult = 1;
        let bits = 0;
        for (let i = 0; i < p.length; ++i) {
            if (msk & (1 << i)) {
                ++bits;
                mult *= p[i];
            }
        }

        const cur = Math.floor(r / mult);
        // Непарна кількість множників — додаємо, парна — віднімаємо
        if (bits % 2 === 1) {
            sum += cur;
        } else {
            sum -= cur;
        }
    }

    return r - sum;
}

Go

func solve(n, r int) int {
	// Знаходимо різні прості множники числа n
	var p []int
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			p = append(p, i)
			for n%i == 0 {
				n /= i
			}
		}
	}
	if n > 1 {
		p = append(p, n)
	}

	sum := 0
	// Перебираємо всі непорожні підмножини множників
	for msk := 1; msk < (1 << len(p)); msk++ {
		mult := 1
		bits := 0
		for i := 0; i < len(p); i++ {
			if msk&(1<<i) != 0 {
				bits++
				mult *= p[i]
			}
		}

		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$ підмножин цілих чисел $a_i$ за $O(n \log r)$ операцій, щоб знайти їхнє найменше спільне кратне, додаючи або віднімаючи кількість його кратних на проміжку. Асимптотика — $O (2^n\cdot n\cdot \log r)$.

Кількість рядків, що задовольняють заданий взірець

Розглянемо $n$ взірців рядків однакової довжини, що складаються лише з літер ($a...z$) або знаків питання. Також задано число $k$. Рядок відповідає взірцю, якщо він має таку саму довжину, що й взірець, і на кожній позиції або відповідні символи рівні, або символ у взірці — це знак питання. Завдання — підрахувати кількість рядків, що відповідають рівно $k$ взірцям (перша задача) та хоча б $k$ взірцям (друга задача).

Спершу зауважимо, що ми легко можемо підрахувати кількість рядків, які задовольняють одразу всі задані взірці. Для цього просто «накладемо» взірці: переберемо позиції («слоти») і подивимося на позицію в усіх взірцях. Якщо всі взірці мають на цій позиції знак питання, то символ може бути будь-якою літерою від $a$ до $z$. Інакше символ цієї позиції однозначно визначається тими взірцями, які не містять знака питання.

Навчимося тепер розв'язувати першу версію задачі: коли рядок має задовольняти рівно $k$ взірців.

Щоб розв'язати її, переберемо й зафіксуємо певну підмножину $X$ із множини взірців, що складається з $k$ взірців. Тоді нам треба підрахувати кількість рядків, які задовольняють цю множину взірців, і лише її, тобто не відповідають жодному іншому взірцю. Ми скористаємося принципом включення-виключення дещо інакше: підсумуємо по всіх надмножинах $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)$$

Однак асимптотика цього розв'язку — $O(3^k \cdot k)$. Щоб її покращити, зауважимо, що різні обчислення $ans(X)$ дуже часто мають спільні множини $Y$.

Ми обернемо формулу включення-виключення і підсумовуватимемо по множинах $Y$. Тепер стає зрозуміло, що та сама множина $Y$ буде врахована в обчисленні $ans(X)$ для $\binom{|Y|}{k}$ множин з однаковим знаком $(-1)^{|Y| - k}$.

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

Тепер наш розв'язок має асимптотику $O(2^k \cdot k)$.

Тепер розв'яжемо другу версію задачі: знайти кількість рядків, що відповідають хоча б $k$ взірцям.

Звісно, ми можемо просто скористатися розв'язком першої версії задачі й додати відповіді для множин розміром більшим за $k$. Однак можна помітити, що в цій задачі множина $|Y|$ враховується у формулі для всіх множин розміром $\ge k$, що містяться в $Y$. З огляду на це, ми можемо записати ту частину виразу, що множиться на $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, 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^k \cdot k)$:

$$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$.

Розглядаючи перешкоду $t$ між $0$ та $i$ ($0 < t < i$), на яку можна наступити, ми бачимо кількість шляхів із $0$ до $i$, що проходять через $t$, у яких $t$ є першою перешкодою між стартом та $i$. Ми можемо обчислити це як: $d[t]$, помножене на кількість довільних шляхів із $t$ до $i$. Кількість «поганих» способів можна підрахувати, підсумувавши це для всіх $t$ між $0$ та $i$.

Ми можемо обчислити $d[i]$ за $O(k)$ для $O(k)$ перешкод, тож цей розв'язок має складність $O(k^2)$.

Кількість взаємно простих четвірок

Дано $n$ чисел: $a_1, a_2, \ldots, a_n$. Потрібно підрахувати кількість способів вибрати чотири числа так, щоб їхній спільний найбільший спільний дільник дорівнював одиниці.

Ми розв'яжемо обернену задачу — обчислимо кількість «поганих» четвірок, тобто четвірок, у яких усі числа діляться на якесь число $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$.

По-перше, одразу перейдемо до оберненої задачі — тобто підрахуємо кількість негармонічних трійок.

По-друге, зауважимо, що будь-яка негармонічна трійка складається з пари взаємно простих чисел і третього числа, яке не є взаємно простим хоча б з одним із цієї пари.

Таким чином, кількість негармонічних трійок, що містять $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$. Тому, щоб обчислити кількість негармонічних трійок, ми підсумовуємо це обчислення по всіх $i$ від $2$ до $n$ і ділимо його на $2$.

Тепер залишилося лише навчитися підраховувати кількість взаємно простих з $i$ на проміжку $[2;n]$. Хоча ця задача вже згадувалася, наведений вище розв'язок тут не підходить — він вимагав би факторизації кожного з цілих чисел від $2$ до $n$, а потім перебору всіх підмножин цих простих чисел.

Швидший розв'язок можливий за допомогою такої модифікації решета Ератосфена:

1. По-перше, знаходимо всі числа на проміжку $[2;n]$ такі, що їхній простий розклад на множники не включає жоден простий множник двічі. Нам також треба знати для цих чисел, скільки множників вони містять.

   • Для цього ми вестимемо масив $deg[i]$ для зберігання кількості простих чисел у розкладі $i$ на множники, та масив $good[i]$, щоб позначити, чи містить $i$ кожен множник не більше одного разу ($good[i] = 1$), чи ні ($good[i] = 0$). Перебираючи від $2$ до $n$, якщо ми доходимо до числа, у якого $deg$ дорівнює $0$, то це просте число і його $deg$ дорівнює $1$.
   • Під час решета Ератосфена ми перебиратимемо $i$ від $2$ до $n$. Обробляючи просте число, ми проходимо всі його кратні й збільшуємо їхні $deg[]$. Якщо одне з цих кратних є кратним квадрата $i$, то ми можемо встановити $good$ як false.

2. По-друге, нам треба обчислити відповідь для всіх $i$ від $2$ до $n$, тобто масив $cnt[]$ — кількість цілих чисел, не взаємно простих з $i$.

   • Для цього згадаймо, як працює формула включення-виключення — фактично тут ми реалізуємо ту саму концепцію, але з оберненою логікою: ми перебираємо компонент (добуток простих чисел із розкладу на множники) і додаємо або віднімаємо його доданок у формулі включення-виключення для кожного з його кратних.
   • Отже, припустимо, ми обробляємо число $i$ таке, що $good[i] = true$, тобто воно бере участь у формулі включення-виключення. Перебираємо всі числа, кратні $i$, і або додаємо, або віднімаємо $\lfloor N/i \rfloor$ від їхнього $cnt[]$ (знак залежить від $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;
}

Python

def solve(n: int) -> int:
    good = [True] * (n + 1)   # чи містить i кожен простий множник не більше разу
    deg = [0] * (n + 1)       # кількість простих чисел у розкладі i
    cnt = [0] * (n + 1)       # кількість чисел, НЕ взаємно простих з i

    ans_bad = 0
    for i in range(2, n + 1):
        if good[i]:
            if deg[i] == 0:
                deg[i] = 1  # i — просте число
            j = 1
            while i * j <= n:
                if j > 1 and deg[i] == 1:
                    if j % i == 0:
                        good[i * j] = False
                    else:
                        deg[i * j] += 1
                # Додаємо або віднімаємо доданок включення-виключення
                cnt[i * j] += (n // i) * (1 if deg[i] % 2 == 1 else -1)
                j += 1
        ans_bad += (cnt[i] - 1) * (n - 1 - cnt[i])

    return (n - 1) * (n - 2) * (n - 3) // 6 - ans_bad // 2

TypeScript

function solve(n: number): bigint {
    const good = new Array<boolean>(n + 1).fill(true); // чи містить i кожен простий множник не більше разу
    const deg = new Array<number>(n + 1).fill(0);      // кількість простих чисел у розкладі i
    const cnt = new Array<number>(n + 1).fill(0);      // кількість чисел, НЕ взаємно простих з i

    let ansBad = 0n;
    for (let i = 2; i <= n; ++i) {
        if (good[i]) {
            if (deg[i] === 0) {
                deg[i] = 1; // i — просте число
            }
            for (let 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] += Math.floor(n / i) * (deg[i] % 2 === 1 ? 1 : -1);
            }
        }
        ansBad += BigInt(cnt[i] - 1) * BigInt(n - 1 - cnt[i]);
    }

    return BigInt(n - 1) * BigInt(n - 2) * BigInt(n - 3) / 6n - ansBad / 2n;
}

Go

func solve(n int) int64 {
	good := make([]bool, n+1) // чи містить i кожен простий множник не більше разу
	deg := make([]int, n+1)   // кількість простих чисел у розкладі i
	cnt := make([]int, n+1)   // кількість чисел, НЕ взаємно простих з i
	for i := range good {
		good[i] = true
	}

	var ansBad int64 = 0
	for i := 2; i <= n; i++ {
		if good[i] {
			if deg[i] == 0 {
				deg[i] = 1 // i — просте число
			}
			for j := 1; i*j <= n; j++ {
				if j > 1 && deg[i] == 1 {
					if j%i == 0 {
						good[i*j] = false
					} else {
						deg[i*j]++
					}
				}
				// Додаємо або віднімаємо доданок включення-виключення
				sign := -1
				if deg[i]%2 == 1 {
					sign = 1
				}
				cnt[i*j] += (n / i) * sign
			}
		}
		ansBad += int64(cnt[i]-1) * int64(n-1-cnt[i])
	}

	return int64(n-1)*int64(n-2)*int64(n-3)/6 - ansBad/2
}

Асимптотика нашого розв'язку — $O(n \log n)$, бо майже для кожного числа до $n$ ми робимо $n/i$ ітерацій у вкладеному циклі.

Кількість перестановок без нерухомих точок (безлади)

Доведіть, що кількість перестановок довжини $n$ без нерухомих точок (тобто жодне число $i$ не стоїть на позиції $i$ — таку перестановку також називають безладом) дорівнює такому числу:

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

(якщо заокруглити цей вираз до найближчого цілого — отримаємо рівно кількість перестановок без нерухомих точок)

Позначимо через $A_k$ множину перестановок довжини $n$ з нерухомою точкою на позиції $k$ ($1 \le k \le n$) (тобто елемент $k$ стоїть на позиції $k$).

Тепер ми скористаємося формулою включення-виключення, щоб підрахувати кількість перестановок із хоча б однією нерухомою точкою. Для цього нам треба навчитися підраховувати розміри перетину множин $A_i$, а саме:

$$\begin{align} \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{align}$$

бо якщо ми знаємо, що кількість нерухомих точок дорівнює $x$, то нам відомі позиції $x$ елементів перестановки, а всі інші $(n-x)$ елементів можна розмістити будь-де.

Підставивши це у формулу включення-виключення і враховуючи, що кількість способів вибрати підмножину розміру $x$ з множини $n$ елементів дорівнює $\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}$$

(оскільки сума в дужках — це перші $n+1$ доданків розкладу $e^{-1}$ у ряд Тейлора)

Варто зауважити, що схожу задачу можна розв'язати в такий самий спосіб: коли треба, щоб нерухомі точки не були серед $m$ перших елементів перестановки (а не серед усіх, як ми щойно розв'язали). Отримана формула така сама, як наведена вище точна формула, але вона йтиме до суми по $k$, а не по $n$.

Задачі для практики

Перелік задач, які можна розв'язати за допомогою принципу включення-виключення:

• UVA #10325 "The Lottery" [difficulty: low]
• UVA #11806 "Cheerleaders" [difficulty: low]
• TopCoder SRM 477 "CarelessSecretary" [difficulty: low]
• TopCoder TCHS 16 "Divisibility" [difficulty: low]
• SPOJ #6285 NGM2 , "Another Game With Numbers" [difficulty: low]
• TopCoder SRM 382 "CharmingTicketsEasy" [difficulty: medium]
• TopCoder SRM 390 "SetOfPatterns" [difficulty: medium]
• TopCoder SRM 176 "Deranged" [difficulty: medium]
• TopCoder SRM 457 "TheHexagonsDivOne" [difficulty: medium]
• SPOJ #4191 MSKYCODE "Sky Code" [difficulty: medium]
• SPOJ #4168 SQFREE "Square-free integers" [difficulty: medium]
• CodeChef "Count Relations" [difficulty: medium]
• SPOJ - Almost Prime Numbers Again
• SPOJ - Find number of Pair of Friends
• SPOJ - Balanced Cow Subsets
• SPOJ - EASY MATH [difficulty: medium]
• SPOJ - MOMOS - FEASTOFPIGS [difficulty: easy]
• Atcoder - Grid 2 [difficulty: easy]
• Codeforces - Count GCD

Відеоматеріали