对连通性容斥

### 应用背景

给出一种等价关系，求全满足/全不满足的方案数。

### 两种情况

常规的容斥，一般有两种情况：

1. 给出一个条件，要求集合内所有元素都不满足这个条件，计数。
2. 给出一个条件，要求集合内所有元素都满足这个条件，计数。

题目条件可能是“弱”的：条件难以完全确定集合的实际分布情况，而钦定某些元素不满足条件更容易处理，所以可以用子集反演公式转为后者。

对等价关系的容斥中，也可以分成这两种情况，类似对子集/超集的容斥。

但是，如果枚举${n \choose 2}$条边容斥就太不划算了。既然是等价关系，可以改为钦定集合划分，组合意义分别是：

1. 钦定一些元素完全不连通。当连通是弱条件时，不连通就是钦定了若干边完全没有，是强条件。
2. 钦定集合划分内所有集合连通。连通是强条件时（比如，全相等），可以钦定连通块后“缩点”。

### 代数表示

反转公式：
$$
\sum_{i=m}^n \begin{bmatrix}n \\ i\end{bmatrix} \begin{Bmatrix}i \\ m\end{Bmatrix}(-1)^{n-i} = [n = m] 
$$
$$
\sum_{i=m}^n \begin{Bmatrix}n \\ i\end{Bmatrix} \begin{bmatrix}i \\ m\end{bmatrix}(-1)^{n-i} = [n = m]
$$
证明：将两类斯特林数带入幂转换的公式，比较系数即可。

显然上面的式子$(-1)^x$部分可以变一变。

#### case 1

令$m = 1$，此时$\begin{bmatrix} i \\ m \end{bmatrix} = (i-1)!$。那么
$$
\sum_{i=1}^n \begin{Bmatrix}n \\ i\end{Bmatrix}(i-1)!(-1)^{i-1} = [n = 1]
$$
令$c(G)$表示某种划分方案G中的连通块数，那么如果我们要求$\sum_G [c(G) = 1]$，就可以求
$$
\begin{aligned}
\sum_G [c(G)=1] &= \sum_G \sum_{i = 1}^{c(G)} \begin{Bmatrix}c(G) \\ i\end{Bmatrix}(i-1)!(-1)^{i-1} \\
&= \sum_{i=1}^n (i-1)!(-1)^{i-1}\sum_G \begin{Bmatrix}c(G) \\ i\end{Bmatrix}
\end{aligned}
$$
而$\sum_G \begin{Bmatrix}c(G) \\ i\end{Bmatrix}$有组合意义：这等价于，先给出一种连通块的集合划分，再在所有合法的G中求出满足这种集合划分的G的个数。“满足”即为：不存在一个连通块被一分为二，也就是要求不同的连通块内没有连边。

#### case 2

令$m = n$，c的定义同上，那么
$$
\begin{aligned}
\sum_G[c(G) = n] &= \sum_G \sum_{i=c(G)}^n \begin{Bmatrix}i \\ c(G)\end{Bmatrix}\begin{bmatrix}n \\ i\end{bmatrix}(-1)^{n-i} \\
&= \sum_{i=1}^n\begin{bmatrix}n \\ i\end{bmatrix}(-1)^{n-i}\sum_G \begin{Bmatrix}i \\ c(G)\end{Bmatrix}	
\end{aligned}
$$
而$\sum_G \begin{Bmatrix}i  \\ c(G)\end{Bmatrix}$有组合意义：这等价于，先给出一种集合划分结果，再将每个连通块作为“点”进一步**任意**划分的方案数。

---

两种case，分别钦定了两个方向（一定连通、一定不连通），得到了不同的结果，又有一定的相关性。

#### 如何套到dp内

普通的容斥，每次只会乘-1的系数，做起来很方便。

对于上面的case1，如果能够做（多项式复杂度的）dp的话，往往可以刻画成：集合间的边一定不能选，集合内的可选可不选。那么可能可以做一个复杂度是$O(n A(n))$，这里A是全局边数的dp。为了体现$(k-1)!$，可以在除最后一次集合划分的转移过程中带上顺序。

对于上面的case2，大概就是不管题目中“不能相同”的条件做一次dp，即可求出$\sum_G \begin{Bmatrix}i  \\ c(G)\end{Bmatrix}$。