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))\)。
标签：le,dfrac,sum,容斥,等价,序列,系数,集合 From： https://www.cnblogs.com/cyffff/p/18357432