容斥原理

容斥原理的定义

设U中有n种不同的属性，第i种属性为$P_{i}$，拥有属性$P_i$的元素构成集合$S_i$，则有

$\left|\bigcup_{i=1}^{n} S_{i}\right|= \sum_{i}\left|S_{i}\right|-\sum_{i<j}\left|S_{i} \cap S_{j}\right|+\sum_{i<j<k}\left|S_{i} \cap S_{j} \cap S_{k}\right|-\cdots +(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|+\cdots+(-1)^{n-1}\left|S_{1} \cap \cdots \cap S_{n}\right|$

即 $\left|\bigcup_{i=1}^{n} S_{i}\right|=\sum_{m=1}^{n}(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|$

容斥原理的证明

$\forall x \in\left[S_{1}, S_{2}, \ldots, S_{m}\right]$，其出现的总次数为

${ Cnt }=\left|\left\{S_{i}\right\}\right|-\left|\left\{S_{i} \cap S_{j} \mid i<j\right\}\right|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k} S_{a_{i}} \mid a_{i}<a_{i+1}\right\}\right| +\cdots+(-1)^{m-1}\left|\left\{S_{1} \cap \cdots \cap S_{m}\right\}\right| \\= C_{m}^{1}-C_{m}^{2}+\cdots+(-1)^{m-1} C_{m}^{m} \\= C_{m}^{0}-\sum_{i=0}^{m}(-1)^{i} C_{m}^{i} \\= 1-(1-1)^{m} \\=1$

---

问题模型举例

HAOI2008 硬币购物

4种面值的硬币，第i种的面值是$C_i$。n次询问，每次询问给出每种硬币的数量$D_i$和一个价格$S_i$，问付款方式的种类数。其中$n \leq 10^{3}, S \leq 10^{5}$

题解

由于所有硬币的面值在初始时都给定了，我们可以预处理出当对于每种硬币的数量不加限制时得到S的方案数。

因为合法的方案数等于总方案数减去不合法的方案数，则问题转化为求出不合法的付款方式的总数。

所以即求解满足 $\sum_{i=1}^{4} C_{i} x_{i}=S-\sum_{i=1}^{k} C_{a_{i}}\left(D_{a_{i}}+1\right)$ 的方案总数

这里则可以套用容斥原理的公式

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int S = 1e5 + 5;
int c[5], d[5], n, s;
int f[S];
signed main() {
  scanf("%lld%lld%lld%lld%lld", &c[1], &c[2], &c[3], &c[4], &n);
  f[0] = 1;
  for (int j = 1; j <= 4; j++)
    for (int i = 1; i < S; i++)
      if (i >= c[j]) f[i] += f[i - c[j]];
  for (int i = 1; i <= n; i++) {
    scanf("%lld%lld%lld%lld%lld", &d[1], &d[2], &d[3], &d[4], &s);
    int ans = 0;
    for (int i = 1; i < 16; i++) {
      int m = s, bit = 0;
      for (int j = 1; j <= 4; j++)
        if ((i >> (j - 1)) & 1) m -= (d[j] + 1) * c[j], bit++;
      if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
    }
    printf("%lld\n", f[s] - ans);
  }
  return 0;
}

---

错位排列计数

对于 $1 \sim n$ 的排列 P 如果满足 $P_{i} \neq i$，则称 P 是 n 的错位排列。求 n 的错位排列数。

题解

问题可转化为求解 $n!-\left|\bigcup_{i=1}^{n} \overline{S_{i}}\right|$，其中 $\overline{S_{i}}$ 即指满足 $P_i=i$ 的排列。

又有

$\left|\bigcap_{i=1}^{k} S_{a_{l}}\right|=(n-k) !$

故得

$\begin{aligned}\left|\bigcup_{i=1}^{n} \overline{S_{i}}\right| &=\sum_{k=1}^{n}(-1)^{k-1} \sum_{a_{1}, \cdots, k}\left|\bigcap_{i=1}^{k} S_{a_{i}}\right| \\ &=\sum_{k=1}^{n}(-1)^{k-1} C_{n}^{k}(n-k) ! \\ &=\sum_{k=1}^{n}(-1)^{k-1} \frac{n !}{k !} \\ &=n ! \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k !} \end{aligned}$

则 n 的错位排列数为

$D_{n}=n !-n ! \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k !}=n ! \sum_{k=0}^{n} \frac{(-1)^{k}}{k !}$

子图染色问题

A 和 B 喜欢对图（不一定连通）进行染色，而他们的规则是，相邻的结点必须染同一种颜色。今天 A 和 B 玩游戏，对于 n 阶完全图 $G=(V,E)$ 。他们定义一个估价函数$F(S)$ ，其中 S 是边集，满足 $S \subseteq E$。$F(S)$ 的值是对图 $G'=(V,S)$ 用 m 种颜色染色的总方案数。他们的另一个规则是，如果 $|S|$ 是奇数，那么 A 的得分增加 ，否则 B 的得分增加 $F(S)$. 问 A 和 B 的得分差值。

题解

首先不考虑限制条件，可以得到 $m^n$ 种不同的染色方案，我们将每个染色方案都看作是一个元素。对于某个染色方案 假如$i,j$两点染的颜色相同，则称该元素属于集合 $Q_{i,j}$。

然后我们回到该题目中，考虑“相邻的结点必须染同一种颜色”，可以理解为若干个集合 Q 的交集。故有

$F(S)=\left|\bigcap_{(i, j) \in S} Q_{i, j}\right|$

然后我们把所有的边 $(i,j)$ 映射到 $T=\frac{n(n+1)}{2}$ 个整数上。这样一来 $Q_{i,j}$ 就映射为 $Q_k$。

于是乎

$F(S) \Leftrightarrow F\left(\left\{k_{i}\right\}\right)=\left|\bigcap_{k_{i}} Q_{k_{i}}\right|$

则可以得到

$A-B =\sum_{K \subseteq M}(-1)^{|K|-1}\left|\bigcap_{k_{i} \in K} Q_{k_{i}}\right| \\ =\sum_{i}\left|Q_{i}\right|-\sum_{i<j}\left|Q_{i} \cap Q_{j}\right|+\sum_{i<j<k}\left|Q_{i} \cap Q_{j} \cap Q_{k}\right|-\cdots+(-1)^{T-1}\left|\bigcap_{i=1}^{T} Q_{i}\right|$

即 $A-B=\left|\bigcup_{i=1}^{T} Q_{i}\right|$

所以有$A-B=m^{n}-A_{m}^{n}$

---

求最大公约数为k的数对个数

设 $1 \leq x, y \leq N$，$f(k)$ 表示最大公约数为 k 的有序数对 $(x,y)$ 的个数，求 $f(1)$ 到 $f(N)$ 的值。

先找到所有以 k 为公约数的数对，再从中剔除所有以 k 的倍数为公约数的数对，余下的数对就是以 k 为最大公约数的数对。

$f(k)=\lfloor(N / k)\rfloor^{2}-\sum_{i=2}^{i * k \leq N} f(i * k)$

所以我们可以倒过来算，从$f(N)$算到$f(1)$。

for (long long k = N; k >= 1; k--) {
  f[k] = (N / k) * (N / k);
  for (long long i = k + k; i <= N; i += k) f[k] -= f[i];
}
for(int i=n;i>=1;i--){
	dp[i]=f(n/i,i);
	for(int j=2;j*i<=n;j++){
		dp[i]-=dp[j*i];
	}
}

---

对于两个关于集合的函数 $f(S)$，$g(S)$，若

$f(S)=\sum_{T \subseteq S} g(T)$

则满足

$g(S)=\sum_{T \subseteq S}(-1)^{|S|-|T|} f(T)$

或者如果有

$f(S)=\sum_{S \subseteq T} g(T)$

那么

$g(S)=\sum_{S \subseteq T}(-1)^{|T|-|S|} f(T)$