集幂学习笔记

· · 算法·理论

肯定要学不然 NOIP 就白打了。

以下默认集合幂级数的项数为 2^n，也就是有 n 个元素，定义 U=\{0,1,2,\dots ,n-1\}，也就是全集。

基本运算

已经过了对应的模板题，讲解上应该没有什么问题。

有交并

使用 FMT 方法，做 n 维前缀和，也可以视作一种另类的 SOSDP，可以在 O(2^nn) 的时间复杂度内完成变换。

即 \operatorname{FMT}(f)_S=\sum_{T\subseteq S}f_T。

定义 f,g 有交并 f*g 为：(f*g)_S=\sum_{L,R\subseteq U,L\cup R=S}f_Lg_R。

不难发现 \operatorname{FMT}(f*g)_i=\operatorname{FMT}(f)_i\operatorname{FMT}(g)_i。

考虑怎么做 IFMT，直接施以高维差分即可。那么我们可以 O(2^nn) 的时间复杂度内完成有交并。

无交并（乘法）

一般而言，集合幂级数的乘法指无交并。

我们定义 f,g 的无交并 f\times g 为：(f\times g)_S=\sum_{L,R\subseteq U,L\cap R=\empty,L\cup R=S}f_Lg_R，比无交并多了一个 L\cap R=\empty 的限制。

或者说，也可以表示为 (f\times g)_S=\sum_{T\subseteq S}f_Tg_{S-T} 是等价的。

注意到在 L\cup R=S 的情况下，L\cap R=\empty 成立等价于 |L|+|R|=|S|。

我们定义集合幂级数 h_f(k) 满足 h_f(k)_S=[|S|=k]f_S。

我们定义 n 个集合幂级数 c_{0,\dots,n-1} 满足 c_i=\sum_{j=0}^i h_f(j)*h_g(i-j)。

那么显然 (f\times g)_S=[x^S]c_{|S|}。

这个技巧我们一般称之为子集卷积。

集幂 \exp 以及 \ln

不少子图计数的基础，你需要知道的是形式幂级数 \exp 以及 \ln 的组合意义，否则会一头雾水。

定义 \exp(f) 是一个满足 \exp(f)=\sum_{i\ge 0}\frac{f^i}{i!} 的集合幂级数，其中 f^i 指的是无交并（之后不再复述）。

类似之前的想法，无交并必然是难处理的，考虑使用有交并的技术。

我们定义 [x^Sy^i]F(x,y) 表示 [x^S]f\times [|S|=i]。

我们定义 x^Sy^i\times x^Ty^j\to x^{S\cup T}y^{i+j}，也就是 x 做有交并，y 做加法卷积。

常规的，我们需要对 x 进行 \operatorname{FMT} 变换，现在 x^Sy^i\times x^Sy^j\to x^Sy^{i+j}。

把 y 当作变元做 \exp 即可。

先假设我们可以用 O(n^2) 的时间复杂度求出一个长度为 n 的形式幂级数的 \exp，来分析复杂度。

发现要做 2^n 次 \exp 和 n 次 \operatorname{FMT}，复杂度均是 O(2^nn^2)。恰好和子集卷积一个复杂度，非常厉害！

思考怎么 O(n^2) 地求 \exp，我们不需要，也没必要使用 O(n\log n) 的多项式方法。

设 g=\exp(f)，对两边求导发现 g'=f'\exp(f)=f'g，推一哈式子：

\begin{aligned} g'&=f'\exp(f)\\ g_{n+1}(n+1)&=\sum_{i=0}^n(i+1)f_{i+1}g_{n-i}\\ g_n&=\frac1n\sum_{i=1}^nif_ig_{n-i} \end{aligned}

可以 O(n^2) 递推，集幂 \exp 即在 O(2^nn^2) 的时间复杂度内完成了。

注意到集幂 \ln 和集幂 \exp 的分析是类似的，只需要会 O(n^2) 递推 \ln 就行了。

等价于知道 g 要求 f：

\begin{aligned} g_n&=f_n+\frac 1n\sum_{i=1}^{n-1}if_ig_{n-i}\\ f_n &=g_n-\frac 1n\sum_{i=1}^{n-1}if_ig_{n-i}\\ \end{aligned}

就一样地递推。

图计数例题

精妙之所在，要理解集幂由子图推向整体的巧妙之处！

应该只有连通二分子图计数没独立切，可能是没留出充足的时间思考。

全部都是口胡，有错的话欢迎 diss。

连通子图计数

Source：经典问题。

给定一个 n 个点，m 条边的图，问有多少种保留边的方案使得图连通。

集幂选手的信心题，学会哈气的第一步。

用 f_S 表示只考虑 S 内的点及其导出子图，连通的方案数，g_S 表示，不一定连通的方案数。

则集幂 g 是好求的，注意到常规 trick 之一个图由若干极大连通子图唯一构成，所以 g=\exp(f)，即 f=\ln g。

施以集幂 \ln 即切之！

连通二分子图计数

Source：ARC105F 加强版。

给定一个 n 个点，m 条边的图，问有多少种保留边的方案使得图是个连通二分子图。

有点难度的题了，学会哈气的第二步。

一个朴素的想法是：我们枚举子图 S，将 S 中的点染成白色，U-S 中的点染成黑色。

而这样染色的必要条件是 S 内部和 U-S 内部必须没有连边。

用 \operatorname{cross}(S,T) 表示其中一个端点在 S，另一个端点在 T 的边数，我们保证 S\cap T=\empty。那么连边方案就是 2^{\operatorname{cross}(S,U-S)}，但是我们忽略了图必须连通的条件，不难发现有 c 个连通块的图会被算 2^c 次。

将一个有 c 个连通块的二分图的权值看作 2^c。

我们设 f_S 为只考虑点集 S 及其导出子图，二分连通子图的个数乘二，g_S 表示二分子图的权值和。

不难发现 g=\exp (f)，f=\ln(g)。

只要能求出 g 就万事大吉了，设 E_S 为 S 的导出子图的边集，那么 g_S=\sum_{T\subseteq S}2^{\operatorname{cross}(T,S-T)}=2^{|E_S|}\sum_{T\subseteq S}2^{-|E_T|}2^{-|E_{S-T}|}。一个子集卷积就做完了。

DAG 子图计数

给定一个 n 个点，m 条边的有向图，问有多少种保留边的方案使得图是个 DAG。

容易的，找时间补。

开始处理有向图问题了，学会哈气的第三步。

考虑刻画拓扑排序，设 f_{S} 表示只考虑 S 内的点及其导出子图，定向出 DAG 的方案数。

每次枚举 T 表示零度点，则容斥系数明显为 (-1)^{|T|+1}。

移一下项发现： $\sum_{T\subseteq S}(-1)^{|T|+1}2^{\operatorname{cross}(T,S-T)}f_{S-T}=-[S=\empty]$。 使用集合幂级数求逆应该就完了。 ### 主旋律 > 给定一个 $n$ 个点，$m$ 条边的有向图，问有多少种保留边的方案使得图是个强连通分量。 > > $n\le 15,m\le n(n-1)$。 经典题，学会哈气的第四步。 我们尝试直接套用上面的思路，用 $f_S$ 表示只考虑 $S$ 内的点及其导出子图，能保留出一个强连通分量的方案数，然后刻画缩点之后的图。 不难发现如果我们缩点之后有超过一个强连通分量，直接不合法了，这显然不是我们想要的，于是考虑用总保留方案数减去有超过一个强连通分量的方案。 $f_S=2^{\operatorname{cross}(S,S)}-\sum_{T\subsetneqq S,T\neq \empty}2^{\operatorname{cross}(T,S-T)}2^{\operatorname{cross}(S-T,S-T)}f_T\times ?$。 $?$ 是我们尚且未知的容斥系数，不好求哇。 那就转换思路，设 $g=-\exp(-f)$。 用 $f,g$ 相互更新： $f_S=2^{\operatorname{cross}(S,S)}-\sum_{T\subseteq S,T\neq \empty}g_T2^{\operatorname{cross}(T,S-T)}2^{\operatorname{cross}(S-T,S-T)}$。 发现 $f_S$ 更新要用到 $g_S$ 但是 $g_S$ 更新要用到 $f_S$？这正是我们想要的，本来就不应该用 $f_S$ 更新自己。 所以直接用 $g_S$ 更新完 $f_S$ 后再用 $f_S$ 把 $g_S$ 补上就好了。 问题在于 $\operatorname{cross}$ 怎么处理，朴素的想法是，对于形如 $\operatorname{cross}(A,A)$ 的东西直接预处理出来。 对于 $\operatorname{cross}(T,S-T)$，直接每次 $S$ 变的时候重新算一下就行，不难。 是 $O(3^n)$ 的。 但是在逛题解区的时候看到了一种更优雅的处理方式，认为有必要写一下。 我们预处理出 $w_S=\sum_{x\in S}3^x$，将 $\operatorname{cross}(T,S-T)$ 映射到 $w_{T}+2w_{S-T}$ 上，形成一个 $3^n$ 的数组，到时候转移和更新都是容易的。 ### 重塑时光 题意好复杂不想重复了。 这不就是主旋律的二元形式吗？ 用 $h_T$ 表示 $T$ 的拓扑序计数，明显可以 $O(2^nn)$ 处理出来。 使用跟主旋律一样的方式处理 $\operatorname{cross}(T,S-T)$，方便起见，令 $c(S,T)=[\operatorname{cross}(S,T)=0]$。 令 $g_{i,S}$ 表示将 $S$ 分成 $i$ 个段，使得这 $i$ 个段之间没有连边的方案数。注意到我们关心最后剩了几个段，所以多存了一维 $i$，这也是和主旋律唯一的区别。 $g_{i,S}$ 的转移是容易的： $$ g_{i,S}=\sum_{T\subseteq S,T\neq\empty,\operatorname{lowbit}(S)=\operatorname{lowbit}(T)}g_{i-1,S-T}h_T[c(S-T,T)\land c(T,S-T)] $$ 然后考虑定义 $f_{i,S}$ 为将 $S$ 分成 $i$ 段使得最后是个 DAG 的方案数。 $$ f_{i,S}=\sum_{j=1}^i\sum_{T\subseteq S,T\neq\empty}g_{j,T}f_{i-j,S-T}(-1)^{j+1}[c(S-T,T)] $$ 就容易做到 $O(3^nn^2)$，更进一步呢？ 我们都说了重塑时光是主旋律的二元版本，我直接拉插一下就好了，其实从 $f$ 和 $g$ 的卷积也可以看出来这是个卷积形式。 代 $n$ 个点值进去跑，最后 $O(n^2)$ 拉插可以做到 $O(3^nn)$。 这样太麻烦了，还是 $O(3^nn^2)$ 好写，怎么卡常呢？ 1. $i$ 只枚举到 $\operatorname{popcount}(S)$，$j$ 枚举到 $\min(\operatorname{popcount}(T),i)$。 2. 用 `unsigned long long` 减少取模次数，而且 `unsigned long long` 本来取模就快点。 3. 精细实现。