正文
我们常见到一类关于等价类划分的容斥问题，大致抽象如下：设集合 \(S\) 大小为 \(n\)，方案集合 \(M\)，对于 \(x\in S\)，有 \(x\) 的方案集合 \(M_x\)，存在定义在 \(M\) 上的等价关系 \(\sim\)。需要求出 \[ \sum_{m_x\in M_x}\prod_{a,b\in S}[m_a\nsim m_b] \]
的值。 对于这类问题，我们有直接做法，即枚举成立的等价关系进行容斥 \[ \sum_{E\subseteq S\times S}(-1)^{|E|}\prod_{S\in C(E)}f(S) \]
其中 \(C(E)\) 是 \(E\) 形成的等价类划分，直观地理解就是边集为 \(E\) 时形成的连通块，每个联通块是一个等价类，\(f(S)\) 则是这个等价类对应地方案集合大小。
这个一般做法是 \(O(4^n)\) 的。但我们会发现 \(C(E)\) 是大量重复的，并且等价于集合划分，因此考虑变换枚举顺序，有
\[ \sum_{P}\prod_{S\in P}f(S)\sum_{E\subseteq S\times S,P=C(E)}(-1)^{|E|} \]
关于后者，首先我们会发现它的贡献对于划分的每一个部分是独立的，因为两两之间不可能有变，否则就属于同一个等价了，所以我们现在只需要对于一个连通块进行考虑，假设其大小为 \(k\)，定义图的价值为 \((-1)^{|E|}\)，\(E\) 为它的边集。那么我们就是要求所有大小为 \(k\) 的连通图的价值和 \(f_k\)。不难联系到连通图计数，对于一般图的价值，我们有
\[ \sum_{i=0}\dbinom{\binom{k}{2}}{i}(-1)^i=(1-1)^{\binom{k}{2}}=[k\le 1] \]
那么对于 \(f_k\) 的 egf
\[ F(z)=\sum_{k\ge 1}f_k\dfrac{z^k}{k!} \]
（其中 \(k\ge 1\) 也是方便讨论，也比较自然，因为在容斥里不会用到 \(f_0\) 的值），有
\[ \exp F(z)=1+z \]
因此
\[ F(z)=\ln(1+z),f_k=[x^k]\ln(1+z)=(-1)^{k-1}(k-1)! \]
那么我们有最后的容斥式子
\[ \sum_{P}\prod_{S\in P}f(S)(-1)^{|S|-1}(|S|-1)! \]
这个直接枚举集合划分的复杂度不低于 \(O(B(n))\)，\(B(n)\) 为 \(\text{Bell}\) 数，大概是 \(O((\dfrac{e^{-0.6+\epsilon}n}{\ln(n+1)})^n)\)，最多处理 \(n\approx 13\)。改用带一定技巧的状压为 \(O(3^n)\)，直接使用集合幂级数的 \(\exp\) 为 \(O(n^22^n)\)。
这个问题应该进一步扩展到图染色问题中（实际上这个问题某种程度是带限制的完全图染色），或者可以用斯特林数，或一些组合解释对这个容斥产生说明。