Principio de inclusión-exclusión

Recursos

Recursos
Fuente	Recurso	Notas
cp-algo	The Inclusion-Exclusion Principle	Artículo bien cubierto
CF	Inclusion-Exclusion Principle	Buena explicación
Wikipedia	Inclusion-exclusion principle	Wiki

Introducción

El principio de inclusión-exclusión se relaciona con hallar el tamaño de la unión de algunos conjuntos.

Verbalmente se puede enunciar de la siguiente forma:

Sumar los tamaños de los conjuntos por separado, restar los tamaños de todas las intersecciones por pares de los conjuntos, volver a sumar los tamaños de las intersecciones de ternas de conjuntos, restar el tamaño de las cuádruplas de conjuntos, …

La identidad matemática de lo anterior es:

\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 |

Escrita en forma compacta:

\bigg|\bigcup_{i=1}^nA_i \bigg|= \sum_{0 \neq J \in \{1, 2,...,n\} } (-1)^{|J|-1} \bigg| \bigcap_{j \in J} A_j \bigg|

Función de Möbius

La función de Möbius es una función multiplicativa que resulta útil al tratar la técnica de inclusión-exclusión y problemas relacionados con divisores. Toma valores en $\{-1, 0, 1\}$ según la factorización del número.

\mu(n)=\begin{cases} 1 & \text{si $n$ es $1$},\\ 0 & \text{si $n$ tiene un factor primo al cuadrado},\\ (-1)^k & \text{si $n$ es producto de $k$ factores primos distintos}. \end{cases}

Abajo se pueden ver los primeros $19$ valores de $\mu(n)$ :

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
$\mu(n)$	1	-1	-1	0	-1	1	-1	0	0	1	-1	0	-1	1	1	0	-1	0	-1

Veamos cómo se puede precomputar la función de Möbius con una criba ligeramente modificada.

C++


mobius[1] = -1;
for (int i = 1; i < VALMAX; i++) {
	if (mobius[i]) {
		mobius[i] = -mobius[i];
		for (int j = 2 * i; j < VALMAX; j += i) { mobius[j] += mobius[i]; }
	}
}

Aplicaciones

SQFREE

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	SQFREE - Square-free integers	Normal	PIE, Divisors	en el módulo

Explicación

Una aplicación perfecta del principio de inclusión-exclusión y de la función de Möbius. En este caso particular el conjunto $A_i$ — mencionado antes en la sección del tutorial — denota cuántos números son divisibles por $i^2$ y se nos pide hallar $\bigg| \bigcup_{i=1}^{\sqrt{n}} A_i \bigg|$ . El arreglo de Möbius precomputado indica si hay que sumar o restar $A_i$ .

Implementación

Complejidad temporal: $\mathcal{O}(V \log V + T \cdot \sqrt{n})$ , donde $V = 1e7$

C++


#include <iostream>
#include <vector>
 
using namespace std;
 
const int VALMAX = 1e7;
 
int mobius[VALMAX];
 
int main() {
	int test_num;
	cin >> test_num;
 
	mobius[1] = -1;
	for (int i = 1; i < VALMAX; i++) {
		if (mobius[i]) {
			mobius[i] = -mobius[i];
			for (int j = 2 * i; j < VALMAX; j += i) { mobius[j] += mobius[i]; }
		}
	}
 
	for (int t = 0; t < test_num; t++) {
		long long n;
		long long ans = 0;
		cin >> n;
		for (int i = 1; 1LL * i * i <= n; i++) {
			ans += mobius[i] * n / ((long long)i * i);
		}
		cout << ans << '\n';
	}
}

Cowpatibility

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Gold	Cowpatibility	Normal	PIE, Bitset	Solución

Explicación

En este caso particular el conjunto $A_i$ — mencionado antes en la sección del tutorial — denota cuántos pares de vacas tienen al menos $i$ sabores de helado en común. Del número total de pares restamos la unión de $A_i$ . La respuesta global es:

\frac{n \cdot(n-1)}{2}- \bigg| \bigcup_{i=1}^{5} A_i \bigg|

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	ifstream in("cowpatibility.in");
	int n;
	in >> n;
 
	map<vector<int>, int> subsets;
	for (int i = 1; i <= n; i++) {
		vector<int> v(5);
		for (int &num : v) { in >> num; }
		sort(v.begin(), v.end());
		for (int mask = 1; mask < (1 << 5); mask++) {
			vector<int> subset;
			for (int i = 0; i < 5; i++) {
				if ((1 << i) & mask) { subset.push_back(v[i]); }
			}
			subsets[subset]++;
		}
	}
 
	long long ans = (long long)n * (n - 1) / 2;
	for (const auto &[subset, freq] : subsets) {
		ans -= ((int)subset.size() % 2 == 1 ? 1LL : -1LL) * freq * (freq - 1) / 2;
	}
 
	ofstream("cowpatibility.out") << ans << endl;
}


from collections import defaultdict
 
with open("cowpatibility.in", "r") as read:
	n = int(read.readline().strip())
	subsets = defaultdict(int)
 
	for _ in range(n):
		flavors = list(map(int, read.readline().strip().split()))
		flavors.sort()
 
		for mask in range(1, 1 << 5):
			subset = tuple(flavors[i] for i in range(5) if (1 << i) & mask)
			subsets[subset] += 1
 
ans = n * (n - 1) // 2
for subset, freq in subsets.items():
	if len(subset) % 2 == 1:
		ans -= freq * (freq - 1) // 2
	else:
		ans += freq * (freq - 1) // 2
 
print(ans, file=open("cowpatibility.out", "w"))

La cantidad de strings que coinciden con un cierto patrón

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	TopCoder	SetOfPatterns	Difícil	PIE, Strings, Patterns	en el módulo

Explicación 1

Un enfoque de programación dinámica con máscaras de bits se vería así:

$dp[i][mask] = \text{la cantidad de strings de longitud i que coinciden con todos los patrones del conjunto, pero con ningún otro patrón. }$ La recurrencia es:

dp[i][mask \& j]=dp[i-1][j]\text{ donde j es un conjunto de patrones que coinciden con el carácter c en la posición i}

El siguiente código ilustra esto:

Implementación

Complejidad temporal: $\mathcal{O}(M \cdot N \cdot 2^N)$ , donde $M$ es el tamaño de cada string en patterns y $N$ es el tamaño de patterns.

C++


const int MOD = 1000003;
 
int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	vector<vector<int>> dp(50, vector<int>(1 << n));
	for (int i = 0; i < m; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			int mask = 0;
			for (int j = 0; j < n; j++) {
				if (patterns[j][i] == c || patterns[j][i] == '?') { mask |= (1 << j); }
			}
			if (i == 0) {
				dp[i][mask]++;
			} else {
				for (int j = 0; j < (1 << n); j++) {
					dp[i][j & mask] = (dp[i][j & mask] + dp[i - 1][j]) % MOD;
				}
			}
		}
	}
 
	int ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		if (__builtin_popcount(mask) == k) { ans = (ans + dp[m - 1][mask]) % MOD; }
	}
 
	return ans;
}

Explicación 2

El problema también se puede resolver usando el principio de inclusión-exclusión.

Una observación importante es que podemos contar fácilmente los strings que satisfacen algunos patrones específicos. Simplemente iteramos por las posiciones de todos los patrones. Si todos los patrones contienen $?$ entonces podemos usar cualquier letra de $a$ a $z$ , lo que nos da $26$ soluciones; en caso contrario solo podemos poner la letra fija contenida por un patrón. La respuesta es el producto.

Iterar sobre subconjuntos — denotados por $A$ — de patrones formados por exactamente $k$ strings. Para este subconjunto específico contar la cantidad de strings que solo pueden coincidir con todos los patrones del subconjunto $A$ . Aplicar el principio de inclusión-exclusión sobre todos los superconjuntos $B$ tales que $A \subset B$ .

solve(A) = \sum_{B \supseteq A} (-1)^{|B|-k} \cdot f(B)

$f(B)$ denota la cantidad de strings que coinciden con al menos el conjunto $B$

La respuesta global es:

ans = \sum_{A:|A|=k} solve(A)

Implementación

Complejidad temporal: $\mathcal{O}(\binom{N}{k} \cdot 2^{N - k} \cdot M \cdot N)$

C++


const int MOD = 1000003;
 
int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	int ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		// subsets with exactly k patterns matters
		if (__builtin_popcount(mask) != k) { continue; }
		// iterate over all superset of current subset mask
		for (int supermask = mask; supermask < (1 << n); supermask++) {
			if ((mask & supermask) != mask) { continue; }
			int sign = ((__builtin_popcount(supermask) - k) & 1 ? -1 : 1);
			int freq = 1;  // checks how many valid strings satisfy the supermask
			for (int i = 0; i < m; i++) {
				bool flag = true;
				char last_letter = '?';
				for (int j = 0; j < n; j++) {
					if (((1 << j) & supermask) == 0) { continue; }
					// check for conflicts if the pattern specifies a letter not '?'
					if (patterns[j][i] != '?') {
						if (last_letter == '?') {
							last_letter = patterns[j][i];
						} else if (patterns[j][i] != last_letter) {
							// conflict! two patterns require different letters here
							flag = false;
							break;
						}
					}
				}
				if (!flag) {
					freq = 0;
				} else if (last_letter == '?') {
					freq = (freq * 26) % MOD;
				}
			}
			ans = (ans + sign * freq) % MOD;
			ans = (ans + MOD) % MOD;
		}
	}
 
	return ans;
}

Fuente	Nombre	Dificultad	Tags	Solución
SPOJ	MOMOS - FEASTOFPIGS	Fácil	PIE, Divisors, Sieve	Solución
SPOJ	KPRIMESB - Almost Prime Numbers Again	Normal	PIE, Divisors	Solución
SPOJ	MSKYCODE - Sky Code	Normal	PIE, Divisors	Solución
CSES	Counting Reorders	Normal	PIE	Solución
CSES	Counting Coprime Pairs	Normal	PIE, Divisors	Solución
CSES	Grid Completion	Normal	PIE	Solución