详细揭秘：集合划分容斥的容斥系数
dp 转移时，我们有时会要求枚举一个极大的合法子集进行转移，但是往往不能很好地处理极大的限制，只能枚举一个不作限制的合法子集。我们希望通过容斥使得每个极大的子集的转移正确。
引用一份看到的形式化描述：在某种等价关系下，对于某一组合结构，构成其的元素其可以被划分成若干等价类，有一关于等价类的系数 $F(x)$（即这一等价类的贡献系数）。而我们的 dp 不能恰好地刻画出每一极大等价类（有可能有相互等价的等价类），记等价类之间的合并关系为 $G(x)$，我们设计容斥系数 $H(x)$ 满足： $$G(H(x))=F(x)$$
例：DAG 定向问题
给你一个 $n$ 个点 $m$ 条边的无向图，给每条边定向并要求不出现环，求定向方案数。
$n\le 18$。
我们知道，这个经典问题的 dp 方法为每一次枚举当前入度为 $0$ 的极大子集 $T$ 将其删去。设 $g_S$ 表示 $S$ 内的点能否入度为 $0$，即 $S$ 是否是独立集，$f_S$ 表示 $S$ 内点的定向方案，有： $$f_S=\sum_{T\sube S} f_{S/T}g_T(-1)^{|T|-1}$$
我们尝试用上述方法得到这个 $(-1)^{|T|-1}$ 的容斥系数：$[x^S]F(x)$ 表示的是极大的入度为 $0$ 的点集为 $S$ 时需要贡献的系数，显然 $[x^S]F(x)=[S\ne \varnothing]$。合并方式为每次加入一个非空无交子集，可以得出 $G(x)=\dfrac{1}{1-x}-1$。所以 $\dfrac{1}{1-H(x)}=F(x)+1$，手动求逆得到 $[x^S]H(x)=(-1)^{|S|-1}$。
设 $A(x)=\displaystyle\sum_Sg_S(-1)^{|S|-1}\cdot x^S$，所求即为 $[x^U]\dfrac{1}{1-A(x)}$。
例：计树
求有多少不同的包含 $n$ 个点的有标号无根树，满足：对于任何一个点 $x$，都存在点 $y$ 使得 $x$ 和 $y$ 之间有一条边且 $|x - y| = 1$。
$n\le 10^5$。
树的形态必定为若干值域连续的链拼起来。
根据 Prufer 定理，$k$ 个大小分别为 $w_{1\dots k}$ 的连通块形成树的方案数为： $$n^{k-2}\prod w_i$$
那么我们每加入一条极长的长为 $w(w\ge 2)$ 的链将答案乘以 $nw$，最后除以 $n^2$。因为我们不能钦定极长，所以需要容斥。
题目要求链长 $\ge 2$，那么 $F(x)=\displaystyle\sum_{i\ge 2}x^i=\frac{x^2}{1-x}$；合并方式与 DAG 定向问题类似，每次直接拼一段上去，$G(x)=\dfrac{1}{1-x}-1$；简单计算得到 $H(x)=\dfrac{x^2}{1-x+x^2}$。
设 $A(x)=\displaystyle\sum_{w}wn\cdot x^w\cdot[x^w]H(x)$，所求即为 $[x^n]\dfrac{1}{1-A(x)}$。
例：Yet Another ABC String
给出 $a,b,c$，求由 $a$ 个 A，$b$ 个 B，$c$ 个 C 构成的字符串数量，使得不存在子串
ABC，BCA和CAB。$a,b,c\le 10^6$。
将序列划分为若干极长的形如 ..BCABC...AB... 的连续段。则每个连续段必须 $\le 2$ 即 $F(x)=x+x^2$，$H(x)=1-\dfrac{1}{1+x+x^2}$。
手玩求逆可以得到： $$[x^i]H(x)=\begin{cases}-1&i\equiv0\pmod3\1&i\equiv1\pmod3\0&i\equiv2\pmod3\end{cases}$$
设 $A(x,y,z)$ 为一个连续段的生成函数： $$\begin{aligned}A(x,y,z)&=-3\sum_{i\ge 1}(xyz)^i+(x+y+z)\sum_{i\ge 0}(xyz)^i\ &=\dfrac{x+y+z-3xyz}{1-xyz} \end{aligned}$$
答案为： $$[x^ay^bz^c]\dfrac{1}{1-A(x,y,z)}$$ $$[x^ay^bz^c]\dfrac{1-xyz}{1-x-y-z+2xyz}$$ $$\sum_{i\ge 0}(-2)^i\left[\binom{a+b+c-2i}{a-i,b-i,c-i,i}-\binom{a+b+c-2i-3}{a-i-1,b-i-1,c-i-1,i}\right]$$
例：Yet Another Permutation Problem
有一个长为 $n$ 的排列 $p$，初始 $p_i=i$，接下来你需要对它进行若干次操作，每次操作你可以指定一个 $x\in[1,n]$，将 $p_x$ 取出后放在排列的开头或末尾。对 $\forall k\in[0,n)$ 求出经过 $k$ 次操作能得到几种不同的排列。
$n\le 1000$。
判断一个排列是否可行，考虑将操作反过来：将排列的开头或末尾任意插入排列中。不难发现排列合法当且仅当存在一个长度 $\ge n-k$ 的上升子区间，将该区间外的数依次向内插入即可。
令 $m=n-k$，不妨计数所有极长上升子区间长度都 $<m$ 的排列数量。$F(x)=\dfrac{x-x^m}{1-x}$，$H(x)=\dfrac{x-x^m}{1-x^m}$。
令 $A(x)$ 为一个上升子区间的 EGF，即 $A(x)=\displaystyle\sum_{i}[x^i]H(x)\cdot \dfrac{x^i}{i!}$，所求即为 $n![x^n]\dfrac{1}{1-A(x)}$。注意到 $A(x)$ 只有 $O(\dfrac{n}{m})$ 项，所以直接暴力求逆也可做到 $O(n^2\log n)$。
例：Distinct Multiples
给定 $n,m$ 以及一个长为 $n$ 的序列 $d_{1\dots n}$，你需要计数有多少个值域为 $[1,m]$ 的序列 $a_{1\dots n}$ 满足 $d_i|a_i$ 且 $a_i$ 两两不同。
$n\le 16$。
考虑令等价类为相等的数的集合，则所有极大等价类大小必须都为 $1$，即 $[x^S]F(x)=[|S|=1]$。注意此处等价类之间的合并是无序的，则 $G(x)=\exp x-1$，$H(x)=\ln\left(F(x)+1\right)$，模拟得 $[x^S]H(x)=(-1)^{|S|-1}(|S|-1)!$。
令 $f_S$ 表示等价类 $S$ 的方案数，$A(x)=\displaystyle\sum_Sf_S(-1)^{|S|-1}(|S|-1)!\cdot x^S$，所求即为 $[x^U]\exp A(x)$。
例：A Nameless Counting Problem
给定 $n,m,x$，求有多少个长为 $n$ 的单调不降序列 $a_{1\dots n}$，满足 $a_n< m$ 且 $\text{xor}_{i=1}^na_i=x$。
$n\le 200$。
考虑不断将序列中相同的数配对删除，最终得到一个单增的序列。一个长为 $k$ 的不重序列对应回原序列的方案数为 $[k\equiv n\pmod2]\dfrac{1}{k!}\displaystyle\binom{m+(n-k)/2}{(n-k)/2}$。
容斥掉互不相同的限制，容斥系数同上题。但此时答案不能简单地由状态的等价类信息得出。设 $f_{i,j,d}$ 表示长为 $i$ 的序列，由高至低考虑到第 $d$ 位，有 $j$ 个数顶着上界 $m$ 时满足 $x$ 这些位的限制的方案数，转移可以枚举这一位有几个数仍顶着上界。
考虑分别有 $i,j$ 个奇偶大小的等价类，则贡献为 $m^jf_{i,0,0}$，则设 $g_{i,j}$ 为目前已经有 $i$ 个数，有 $j$ 个奇数大小等价类的贡献和。等价类之间无序，转移时枚举包含 $1$ 的等价类大小即可。
时间复杂度 $O(n^3\log v)$，使用生成函数刻画可以得到更优的做法。
例：异或图
给定一个 $n$ 个点 $m$ 条边的图以及一个长为 $n$ 的序列 $a_{1\dots n}$，有一常数 $C$，你需要求出有多少序列 $b_{1\dots n}$ 满足 $0\le b_i\le a_i$，$\forall (u,v)\in E,b_u\ne b_v$，$\text{xor}_{i=1}^nb_i=C$。
$n\le 15$。
考虑 $m=0$ 怎么做，从高至低枚举第一个不全顶到上界的位 $d$，则低 $d-1$ 位只需要一个在第 $d$ 位不顶到上界的数进行调整，其余数任选即可。
令等价类为相等的数的集合，则 $[x^S]F(x)$ 等于 $1$ 当且仅当 $S$ 内点在图上为独立集。$H(x)=\ln (F(x)+1)$ 可以直接求出。
考虑一个状态的答案，我们只关注每个等价类内部的最小值。每个大小为偶数的等价类均可随便取，大小为奇数的等价类的最小值（称为关键点）构成 $m=0$ 的子问题。
设 $f_{S,T}$ 表示当前已经考虑了 $S$ 内的点，其中关键点的集合为 $T$ 的方案数，时间复杂度为 $O(4^n)$。
此时记录了大量无用信息，我们将 $a$ 从小到大排序，逐个尝试加入关键点。设当前加入到 $i$，则 $[1,i)$ 的点已经必然在考虑的点集中，只需要记录它们是否在关键点集中；$[i,n]$ 的点必然不在当前关键点集中，只需要记录它们是否在已考虑点集中。这样状态数就减小至 $2^n$，再加上枚举子集，时间复杂度为 $O(3^nn+2^n(m+n\log V))$。