芳乃可爱捏。
近日发现自己的计数水平真的差的没边，索性开了个专题专门来记容斥。
容斥方法
小学奥数
回到原始的集合计数。在集合 $n\le 3$ 时观察 Venn 图有优美结论：
把这个进一步扩展，有
如上是对于「集合大小」这一特殊性质的容斥原理。即 $f(S)=\vert S\vert$，下面给出满足上式的 $f$ 的一般条件：
实际上还有更深一步的条件，但限于篇幅讨论范围，暂且不提。
于是有这类套路的容斥方法：给定条件求全部满足的对象数。
答案为 所有对象 - 至少不满足一个的 + 至少不满足两个的 - 至少不满足其中三个的 …
凑容斥系数
对于给出物品，求满足某个条件 $C_0$ 下所有物品贡献之和。一般的方法是构造些容易计算的条件 $C_1,\cdots,C_n$，然后构造容斥系数 $f_i$，使得对于 每个物品 有：
$$\sum\limits_{i=1}^n g(C_i)f_i=g(C_0)$$
$g(C_i)$ 即为在 $C_i$ 条件下，选定物品的贡献（注意此情景下是单一物品的贡献）。
错排问题
求长度为 $n$ 的排列使得任意 $p_i\not=i$ 的排列 $p$ 个数。
目标条件 $C_0$ 就是存在 $0$ 个 $i$ 使得 $p_i=i$，也就是错排个数。
设计 $C_i$ 表示存在 $i$ 个使得 $p_i=i$。对于一个固定的排列 $p$，设其恰好有 $m$ 个 $p_i=i$ 的 $i$，$g(C_i)$ 是容易计算的，为 $\dbinom mi$。但深究为啥 $g(C_i)=\dbinom mi$，实际上在对于所有不动点进行枚举时，该排列被枚举的次数就是如此。于是有
容易解得 $f_i=(-1)^{i+1}$。
设恰有 $i$ 个位置满足 $p_i\not=i$ 的排列贡献为 $a_k$，求所有 $n$ 阶排列贡献之和。
有 $\sum\limits_{i=0}^m\dbinom{m}{i}f_i=a_m$
容易 $\mathcal O(n^2)$ 地递推出 $f$，答案为 $\sum\limits_{i=0}\dbinom ni(n-i)!f_i$。
笔者对容斥的理解有限，只好愚笨地复制 ppt 的内容了。
反演
二项式反演
例题
CF1228E Another Filling the Grid
直接做的是二维的二项式反演，下面讲一下更优美的方法。
行行之间互不干扰，不妨使行行合法。钦定 $i$ 列不合法，那么先选 $i$ 个。由于行行独立，不妨继续考虑一行的方案数。有 $i$ 列是不合法，剩下的 $n-i$ 列随便，为保证行合法要减去一行都不为 $1$ 的方案，即 $(k-1)^i\cdot k^{n-i}-(k-1)^n$。然后你发现有 $n$ 行，于是就是这个东西的 $n$ 次方，再在外面套个组合数。反演一下就有
$$Ans=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}((k-1)^i\cdot k^{n-i}-(k-1)^n)^n$$
DP 容斥对象
P4448 [AHOI2018初中组] 球球的排列
给出 $m$ 个球，每个球有颜色 $a_i\in[1,n]$。球有编号，求多少种分配顺序使得任意相邻球异色。 $m\le 2000$。
实际上这是已经转化过的题意了。下面简单等价一下。
若 $xy=a^2$ 且 $xz=b^2$，则 $x^2yz=a^2b^2$。于是 $yz=\left(\dfrac{ab}{x}\right)^2$。其实到这里就可以说明 $yz$ 亦是平方数，但是进一步取 $x$ 与 $ab$ 的质因子交集，就可严格证明。
直接钦定是混乱的，考虑一种求方案的惯用手法——捆绑法。不妨把相邻同色的捆绑在一起，这样在刻画状态时更容易处理。设 $b_i$ 表示颜色 $i$ 形成的块数，令 $B=\sum\limits_{i=1}^n b_i$。
假定已确定一组状态 $(b_1,b_2,\cdots,b_n)$，先考虑一种颜色的贡献。考虑划分每个块的大小，再进行相对排列。根据插板，有 $a_i!\dbinom{a_i-1}{b_i-1}$。扩展到多种颜色，那么实际上还要对这所有格块进行排序划分。即 $B!\prod a_i!\dbinom{a_i-1}{b_i-1}\dfrac{1}{b_i!}$。$\dfrac 1{b_i!}$ 的系数是抵消同种色块的相对排序。
发现如果固定 $B$，转移中 $b_i$ 与 $b_{i-1}$ 之间无关，于是设 $f(i,j)$ 表示用了前 $i$ 个颜色的 $\sum\limits_{k=1}^i b_k=j$。枚举 $j$ 以及当前块数 $k$，有转移 $f(i,j+k)\gets f(i-1,j)\times a_{i}\dbinom{a_i-1}{b_i-1}\dfrac{1}{b_i!}$，最终给所有的 $f(n,k)$ 乘上一个系数 $k!$。由于 $m=\sum a_i$，所以事实上复杂度是 $\mathcal O(m^2)$ 的。
对于 $f(n,k)$，由于第一维始终为 $n$，在接下来的叙述中略去这一维度。
考虑容斥的经典形式 $f(S)=\sum\limits_{T\subseteq S} g(T)\iff g(S)=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -\vert S\vert}f(T)$。套到这道题上，注意到 $f(k)$ 实则上是对所有大小为 $k$ 的集合 $\vert S\vert$ 的和，$g(S)$ 同理。于是直接进行容斥，$g(k)$ 表示 $B=k$ 的方案数。有 $g(B)=\sum\limits_{i=1}^{B}(-1)^{B-i}f(i)$，$g(m)$ 即为答案。
AT_arc101_c [ARC101E] Ribbons on Tree
给出树，将点两两配对，使配对的点路径集体 $+1$。求使边权都不为 $0$ 的方案数。
$n\le 5000$。
正着显然不好做，考虑容斥。设 $f(S)$ 表示钦定选 $S\subseteq E$ 的边权为 $0$ 的方案数，设 $g(S)$ 表示恰好有 $S\subseteq E$ 边权为 $0$ 的方案数。
我们所求的是没有边权为 $0$ 的，即 $g(\emptyset)=\sum\limits_{S\subseteq E}(-1)^{\vert S\vert}f(S)$。
于是考虑求 $\sum\limits_{S\subseteq E}(-1)^{\vert S\vert}f(S)$ 这一坨东西。实际上这样会划分出若干个连通块，由于两两配对，因此连通块大小必然是偶数。考虑一个连通块的贡献 $h(\vert G’\vert)$，设连通块大小为 $2k$，那么就是两两配对的方案数，考虑全排列去掉排列再去掉两两排列，有 $g(2k)=\dfrac{(2k)!}{k!2^k}=(2k-1)!!$。
而 $f(S)$ 就是划分出的连通块的 $g$ 的乘积。考虑 dp，设 $dp_{u,i}$ 表示 $\operatorname{subtree}(u)$ 中 $u$ 所在连通块大小为 $i$，且 $u$ 所在连通块未进行配对，考虑其子树内所有连通块加权计算后结果。
- 连接。那么直接转移 $dp’{u,i+j}\gets dp’{u,i+j}+ dp_{u,i}\times dp_{v,j}$。
- 断开。那么要计算 $v$ 所在连通块的贡献，然后在计算：$dp’{u,i}\get dp’{u,i}-dp_{u,i}\times(\sum\limits_{j\bmod 2=0}dp_{v,j}\times(j-1)!!)$
最终答案就是 $\sum\limits_{k\bmod2=0}dp_{root,k}\times (k-1)!!$。