子集反演学习笔记

· · 个人记录

子集反演

定义 [x] 表示集合 \{i|1 \le i \le x, i \in \mathbb{Z^*}\}。

设 S \subset [n]。有：

f(S)=\sum_{T \subset S}g(T) \iff g(S)=\sum_{T \subset S}(-1)^{|S|-|T|}f(T) f(S)=\sum_{T \supset S}g(T) \iff g(S)=\sum_{T \supset S}(-1)^{|T|-|S|}f(T)

证明：

只证明第一个式子，第二个与第一个类似。

\begin{aligned} \sum_{T \subset S}(-1)^{|S|-|T|}f(T) &= \sum_{T \subset S}(-1)^{|S|-|T|}\sum_{Q \subset T}g(Q)\\ &= \sum_{Q \subset S}g(Q)\sum_{Q \subset T \subset S}(-1)^{|S|-|T|}\\ &= \sum_{Q \subset S}g(Q)\sum_{T \subset (S / Q)}(-1)^{|S / Q|-|T|}\\ \end{aligned}

观察 \sum_{T \subset (S / Q)}(-1)^{|S / Q|-|T|} 发现当 S / Q = \emptyset 时为 1，否则为 0。两两配对可以证明。

所有除了 S = Q，其它的都是 0，所以原式就等于 g(S)，得证。

应用

子集反演的核心：包含与恰好之间的转化。

问题： m 个数 p_1 \sim p_m，求 1 \sim n 中多少个数被奇数个 a_i 整除。

思路：

设 S \subset [m]。

f(S)=|{\{x | 1 \le x \le n, \forall i \in S,p_{i}|x\}}| g(S)=|{\{x | 1 \le x \le n, \forall i \in S,p_{i}|x,\forall i \not \in S,p_i \not | S}\}|

答案就是 \sum_{|S| \bmod 2 = 1}g(S)。

但是 g 不好求，但是 f 很好求，容易得到：

f(S)=\frac{n}{\prod_{i \in S}p_i}

我们考虑用 f 表示 g。

根据定义，可以得到：

f(S)=\sum_{S \subset T}g(T)

然后子集反演，得到：

g(S) = \sum_{S \subset T}(-1)^{|T| -|S|}f(T)

这样就可以求出 g 了。

但是还可以更进一步，我们将结果代入答案中得到：

\begin{aligned} \sum_{|S| \bmod 2 = 1}g(S) &= \sum_{|S| \bmod 2 = 1}\sum_{S \subset T}(-1)^{|T| -|S|}f(T)\\ &= \sum_{|S| \bmod 2 = 1}\sum_{S \subset T}(-1)^{|T| + |S|}f(T)\\ &= \sum_{T\not = \emptyset}f(T)\sum_{|S| \bmod 2 = 1,|S| \subset T}(-1)^{|T| + |S|}\\ &= \sum_{T\not = \emptyset}f(T)\sum_{i=1}^{\lceil \frac{|T|}{2}\rceil}\binom{|T|}{2i-1}(-1)^{|T|+2i-1}\\ &= \sum_{T\not = \emptyset}f(T)(-1)^{|T|-1}\sum_{i=1}^{\lceil \frac{|T|}{2}\rceil}\binom{|T|}{2i-1}\\ \end{aligned}

而 \sum_{i=1}^{\lceil \frac{|T|}{2}\rceil}\binom{|T|}{2i-1} 其实就等于 2^{|T|-1}，也就是 |T| 的子集中刚好大小为奇数和偶数的各占一半。

经过化简，最终得到：

\sum_{T\not = \emptyset}f(T)(-2)^{|T|-1}

然后做完了。

问题： 求 n 个点有标号的 DAG 个数。

思路：

设 S \subset [n]。

$g_n(S)$：有多少个 $n$ 个点的 DAG，使只有 $S$ 的点入度为 $0$。 可以得到： $$ f_n(S)=\sum_{S \subset T}g_n(T) $$ 所以： $$ g_n(S) = \sum_{S \subset T}(-1)^{|T| -|S|}f_n(T) $$ 首先，我们可以得到： $$f_n(S)=2^{|S|(n-|S|)}f_{n-|S|}(\emptyset)$$ 将所有点分成两部分，$S$ 只能往外连，剩下的内部连。 我们最后要求的应该是 $f_n(\emptyset)$。 结合上面的式子，我们可以得到： $$ \begin{aligned} f_n(\emptyset) &= \sum_{T}g_n(T)\\ &= \sum_{T \not= \emptyset}g_n(T)\\ &= \sum_{S \not= \emptyset}\sum_{S \subset T}(-1)^{|T|-|S|}f(T)\\ &= \sum_{S \not= \emptyset}\sum_{S \subset T}(-1)^{|T|+|S|}2^{|T|(n-|T|)}f_{n-|T|}(\emptyset)\\ &= \sum_{T \not= \emptyset}[\sum_{S \subset T,S \not= \emptyset}(-1)^{|S|}](-1)^{|T|}2^{|T|(n-|T|)}f_{n-|T|}(\emptyset)\\ &= \sum_{T \not= \emptyset}(-1)(-1)^{|T|}2^{|T|(n-|T|)}f_{n-|T|}(\emptyset)\\ &= \sum_{T \not= \emptyset}(-1)^{|T|+1}2^{|T|(n-|T|)}f_{n-|T|}(\emptyset)\\ &= \sum_{k=1}^n\binom{n}{k}(-1)^{k+1}2^{k(n-k)}f_{n-k}(\emptyset) \end{aligned} $$ 这样就可以 $O(n^2)$ 转移了。