什么是容斥
大概就是一种计数方式，我们利用比较简单的方法求得满足部分性质的答案
然后在我们将这些答案加起来想要得到总答案的时候，我们发现有些东西被重复计算了
而这时候我们需要在每一个部分答案上乘上容斥系数，这样才能保证加起来折后没有东西被重复计算
容斥的本质是反演
至于为什么这样说，我们来看几个例子
反演
莫比乌斯反演
$f_n=\sum_{d|n} g_d\Leftrightarrow g_n=\sum_{d|n} \mu_{\frac{n}{d}} f_d$
$f_n=\sum_{n|d}g_d\Leftrightarrow g_n=\sum_{n|d} \mu_{\frac{d}{n}}f_d$
证明：
例题
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求所有子序列的价值的和，一个子序列如果长度为 $k$，且 $gcd$ 为 $d$，那么这个子序列的价值为 $k\times d$
$n\le 2\times 10^5,a_i\le 10^6$
简要题解：令 $g_n$ 表示 $gcd$ 是 $n$ 的每个序列的价值，这里为了方便计算，我们把 $n$ 提出来
即最终答案为 $\sum_{i=2}^n ig_i$
我们考虑求 $f_n=\sum_{n|d}g_d$，这个东西我们可以直接枚举 $n$ 的倍数，算出有多少数是 $n$ 的倍数，不妨设有 $s$ 个，那么 $f_n=\sum_{i=1}^s i\binom{s}{i}=s2^{s-1}$，然后我们再反演回去求出 $g_n$ 即可，时间复杂度 $O(n\log n)$
简要题意：给定 $x$ 和 $y$，求有多少序列，满足 $gcd$ 是 $x$，和是 $y$，序列中的数必须是正整数
$1\le x,y \le 10^9$
简要题解：然后我们考虑容斥，令 $f(n)$ 表示和为 $m$，$gcd$ 是 $n$ 的倍数的序列的数量，$g(n)$ 表示和为 $m$，$gcd$ 是 $n$ 的序列的数量那么答案就是 $g(1)$
容易写出 $f(n)$ 的式子，$f(n)=\sum_{n|d}g(d)=2^{\frac{m}{n}-1}$
根据莫比乌斯反演，$g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$
注意到数列的 $gcd$ 一定是和的约数，所以 $g(1)=\sum_{d|m}\mu(\frac{d}{m})f(d)$
简要题意：给定 $n$ 和 $n$ 个区间 $[l_i,r_i]$ 以及一个整数 $m$，求有多少长度为 $n$ 的序列 $a_i$ 满足 $l_i\le a_i\le r_i$ 且 $\sum_{i=1}^na_i\le m$ 且 $gcd(a_1,\cdots,a_n)=1$
$n\le 50,m\le 10^5,l_i\le r_i\le m$
简要题解：我们考虑直接容斥，每次计算 $gcd$ 是 $d$ 的倍数的方案，最后拿 $\mu$ 容斥一下即可，所以我们枚举 $d$，注意对于 $d=1$ 的 $dp$ 我们可以通过前缀和优化做到 $O(nm)$，那么对于 $d$ 不等于 $1$，我们也可以做到 $O(\lfloor\frac{nm}{d}\rfloor)$，那么总时间复杂度 $O(nm\log m)$，另外需要注意 $[l_i,r_i]$ 对于 $d$ 能选的数的个数为 $[\lceil \frac{l_i}{d}\rceil,\lfloor\frac{r_i}{d}\rfloor]$
二项式反演
$f_k=\sum_{i=0}^k(-1)^i\binom{k}{i}g_i\Leftrightarrow\sum_{i=0}^k(-1)^i\binom{k}{i}f_i$
$f_k=\sum_{i=0}^k\binom{k}{i}g_i\Leftrightarrow g_k=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}f_i$
$f_k=\sum_{i=k}^n\binom{i}{k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i$
证明：
剩下的式子证明类似
例题
简要题意：现在有一个含有 $n$ 个元素的集合，我们要从这个集合中所有 $2^n$ 个子集中选出若干个，使得他们的交集元素个数为 $k$，求有多少种选法
$n\le 10^6$
简要题解：我们考虑容斥，令 $f_k=\sum_{i=k}^n \binom{i}{k}g_i$，其中 $g_k$ 为交集的元素个数恰好为 $k$ 的方案数，则答案为 $g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_k$
容易得到 $f_k=\binom{n}{k}2^{2^{n-k}}$
简要题意：给定一个 $n\times m$ 矩阵，矩阵中每个点可以染成 $k$ 种颜色中的某一种，求没有任意一行或任意一列颜色相同的方案数
$n,m\le 10^6,k\le 10^9$
简要题意：我们令 $g_{r,c}$ 表示恰好有 $r$ 行和 $c$ 列颜色相同，答案即为 $g_{0,0}$
我们考虑求 $f_{r,c}=\sum_{i=r}^n\sum_{j=c}^m\binom{i}{r}\binom{j}{c}g_{i,j}\Leftrightarrow g_{r,c}=\sum_{i=r}^n\sum_{j=c}^m(-1)^{i-r}\binom{i}{r}(-1)^{j-c}\binom{j}{c}f_{i,j}$，$f_{r,c}$ 求法如下
1
2
3
4if(!r && !c) f[r][c] = pow_mod(k, n * m);
else if(r > 0 && !c) f[r][c] = C(n, r) * pow_mod(k, r) * pow_mod(k, (n - r) * m);
else if(c > 0 && !r) f[r][c] = C(m, c) * pow_mod(k, c) * pow_mod(k, n * (m - c));
else f[r][c] = C(n, r) * C(m, c) * k * pow_mod(k, (n - r) * (m - c)); //行和列有重合，所以必须是一个颜色我们分情况讨论一下，得到下面这个式子
$g_{0,0}=k^{nm}+\sum_{i=1}^n(-1)^i\binom{n}{i}k^{m(n-i)+i}+\sum_{i=1}^m(-1)^i\binom{m}{i}k^{n(m-i)+i}+\sum_{i=1}^n\sum_{j=1}^m(-1)^{i+j}\binom{n}{i}\binom{m}{j}k^{(n-i)(m-j)}$
后面那两个求和，可以利用二项式定理化成 $\sum_{i=1}^n(-1)^i\binom{n}{i}[(k^{n-i}-1)^m-k^{(n-i)m}]$ ，时间复杂度 $O(n\log n)$
简要题意：如果一个排列满足对于所有的 $i$，都有 $|P_i-i|\neq k$，则称排列 $P$ 合法，现在给定 $n$ 和 $k$，求有多少合法排列
$2\le n\le 2000,1\le k\le n - 1$
简要题解：考虑容斥，我们令 $f_i$ 表示至少有 $i$ 个位置满足 $|P_i-i|=k$，$g_i$ 表示恰好有 $i$ 个位置满足 $|P_i-i|=k$，所求即为 $g_0=\sum_{i=0}^n(-1)^if_i$
我们考虑如何求 $f_i$，我们考虑原问题转化，考虑二分图左部点表示 $P$，右部点表示 $1$ 到 $n$，我们将左部点 $i$ 连向右部点 $i-k$ 和 $i+k$，容易发现，会影响的点是若干条链，根据组合数学经典式子，可以得到 $n$ 个点链，选择 $m$ 条互不相邻的边的方案数是 $\binom{n-m}{m}$，那么 $f_i$ 就是一个直接按照背包的做法合并即可
时间复杂度 $O(n^2)$，使用多项式快速幂可以做到 $O(n\log n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，问有多少排列 $p$ 满足对于所有 $i\in[2,n]$，$a_{p_{i-1}}\times a_{p_i}$ 不是完全平方数
$n \le 300,a_i\le 10^9$
简要题解：我们考虑首先将每个数出现偶数次的质因子都去掉后，容易得到满足条件的排列是相等的数不能相邻的排列
那么题意被我们转换成求一个类似多重集的交错排列的东西，我们考虑组合容斥
令 $f_k$ 表示至少有 $k+1$ 个相同的数相邻，$g_k$ 表示恰好有 $k+1$ 个相同的数相邻
容易得到 $f_k=\sum_{i=k}^{n}\binom{i}{k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i$，答案即为 $g_0=\sum_{i=0}^n(-1)^if_i$
我们考虑对于 $m$ 个相同的数，我们将其分为 $k$ 个连续段，那么他们对答案的贡献是 $m-k$
所以我们考虑这样求 $f$，我们求所有数中至少有 $k$ 个连续段的排列个数为 $h_k$，容易得到 $h_k=f_{n-k}$
对于 $h$，我们考虑指数生成函数，那么容易得到对于一种数字，不妨设其有 $m$ 个，那么它的指数生成函数就是 $F(x)=\sum_{i=1}^{m}m!\binom{m-1}{i-1}\frac{x^i}{i!}$，我们把所有数字的生成函数卷起来即可，因为 $\sum m =n$，所以这部分可以做到 $O(n\log ^2n)$，总的时间复杂度为 $O(n\sqrt a_i+n\log ^2n)$
min-max容斥
其中 $\max_S$ 表示集合 $S$ 的最大值，$\min_S$ 表示集合 $s$ 的最小值
$\max_{S}=\sum_{\emptyset \neq T\subseteq S}(-1)^{|T|+1}\min_T$
$\min_S=\sum_{\emptyset \neq T\subseteq S}(-1)^{|T|+1}\max_T$
证明：
这里只证明第一个式子，第二个式子的证明类似，不妨设集合大小为 $n$，第 $i$ 小的元素为 $a_i$
注意到 $a_k$ 的系数为 $\sum_{i=1}^{n-k+1}(-1)^{i+1}\binom{n-k}{i-1}=\sum_{i=0}^{n-k}(-1)^i\binom{n-k}{i}=[n=k]$，这里 $i$ 枚举的是 $a_k$ 作为最小值的集合的大小
另外注意到这里的 $min$ 和 $max$ 不只是数字的大小比较，可以是任意一种偏序关系
广义min-max容斥
其中 $\rm kmax_S$ 表示集合 $S$ 的第 $k$ 大值，$\rm kmin_S$ 表示集合 $S$ 的第 $k$ 小值
$\rm kmax_S=\sum_{\emptyset \neq T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min_T$
$\rm kmin_S=\sum_{\emptyset \neq T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max_T$
期望意义下的 min-max 容斥
需要注意期望意义下 $\min-\max$ 容斥也是成立的，$E(\max_S)$ 为集合 $S$ 的最大值的期望，$E(\min_S)$ 为集合 $S$ 的最小值的期望
例题
简要题意：刚开始你有一个数字 $0$，给定一个整数 $n$ 以及 $[0,2^n-1]$ 的每个数字生成的概率，每秒随机生成一个数字与手上的数字或，问期望多少秒手上的数字变为 $2^n-1$
$n\le 20$
简要题解：我们考虑 $min-max$ 容斥，我们另一个数字的大小表示它出现的时间
那么我们现在要求最大值 $\max_S$，我们发现这个东西不好求，我们考虑求最小值 $\min_S$
容易得到 $\min_S=\frac{1}{\sum_{T\cap S\neq \emptyset}p[T]}=\frac{1}{1-\sum_{T\subseteq (U-S)}p[T]}$，注意到这样的 $T$ 是 $S$ 的补集的子集，也就是说我们只需要求一个高维前缀和即可，时间复杂度 $O(n2^n)$
简要题意：现在有 $n$ 种物品，每个单位时间，有 $\frac{p_i}{m}$ 生成第 $i$ 中原料，求期望多少时间我们可以收集 $k$ 种不同的物品
$k\le n\le 1000,n-k\le 10,\sum p_i = m,m\le 10000$
简要题解：我们考虑 $\max-\min$ 容斥，那么我们相当于要求第 $k$ 小，但是我们注意到 $n-k$ 很小，那么我们可以转换为求第 $n-k+1$ 大，然后我们考虑 $\rm kmax_S$ 的式子，$\rm kmax_S=\sum_{\emptyset \neq T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min_T$，我们知道 $\min_S$ 为 $\frac{m}{\sum_{x \in S}p_x}$，我们考虑 $dp$ 计数这些东西，因为 $min_S$ 的值在分母上，所以我们必须把 $\sum p$ 记录到 $dp$ 式子里，同时我们注意到有一个 $\binom{|T|-1}{k-1}$ 我们考虑递推这个东西，那么我们需要记录三维，$f_{i,j,k}$ 表示第 $i$ 个物品，$\sum p =j$，$k$ 的值为 $k$，这个东西可以 $O(1)$ 转移，时间复杂度 $O(10nm)$，需要注意 $dp$ 的初值
子集反演
$f_S=\sum_{T\subseteq S}g_T\Leftrightarrow g_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}f_T$
例题
简要题意：$n$ 人围成一圈，每个人独立随机地选择一名其他玩家并向其开一枪，开枪是同时的，被命中者立刻阵亡退出游戏，假设所有人的命中概率都为 $p$，问还剩 $k=0,1,2,\cdots,n$ 个人 的概率.
$n\le 3\times 10^5$
简要题解：我们考虑容斥，不必精确的计算到底有那些人还活着，我们考虑定义 $f(S)$ 表示只有集合 $S$ 里的人被枪击，有多少人活着不作考虑，$g(S)$ 表示集合 $S$ 里的人死了，容易得到 $f(S)$ 中死掉的人一定是 $S$ 的子集，可以得到子集反演 $g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)$
$f(S)$ 较为容易计算，$f(S)=(1-p+\frac{p(|S|-1)}{n-1})^{|S|}(1-p+\frac{p|S|}{n-1})^{n-|S|}$，大概就是将人分为圈外和圈内，然后每个人没有命中活着命中圈内的人
可以发现 $f(S)$ 只跟集合大小有关系，$g(S)=\sum_{i=0}^{|S|}(-1)^i\binom{|S|}{i}f(i)$，这显然是一个卷积的形式，答案就是 $\binom{n}{|S|}g(|S|)$，时间复杂度 $O(n\log n)$
简要题意：现在有 $n$ 个城市，有 $n-1$ 个公司来修路，每个公司可以修某些路，现在要求恰好修 $n-1$ 条路使这 $n$ 个城市连通并且每个公司恰好其中一条路的方案数
$n\le 17$
简要题解：我们考虑枚举这次负责修路的公司 $S$，然后用矩阵树定理算出总的方案数 $f_{S}$，令 $g_{S}$ 表示 $S$ 中的每个公司都至少修了一条路的方案数，容易得到 $f_{S}=\sum_{T\subseteq S} g_T$，根据子集反演，可以得到 $g_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}$
因为恰好有 $n-1$ 个公司，所以答案就是 $g_U$，$U$ 表示这 $n-1$ 个公司的集合，时间复杂度 $O(2^nn^3)$