集合幂级数与子图连通问题

· · 算法·理论

参考 cxy APIO 课件和 lgx 不知道从哪里搞来的什么课件，还有网上的众多博客。

集合幂级数

通俗讲就是状压。

可以用 FWT 进行一些简单运算，比如 OR/XOR/AND 卷积。

子集卷积

即求 H_S=\sum_{T\in S} F_TG_{S/T}=\sum_{A\ \text{or}\ B = S,A\ \text{and}\ B=\empty}F_AG_B。A\ \text{and} \ B=\empty 相当于 |A|+|B|=|S|，那么可以将 F,G 按照大小分成 n 组，然后对于每个大小分别 FWT，得到 H 按照大小分成 n 组的结果，对于 H_S 取 H 中大小为 |S| 的组中的 S，复杂度 O(2^nn^2)。

子集卷积逆

要求 A_0=1,C_0=1。

已知 A\times B=C 和 A,C，求 B。设 A^{-1} 使得 A\times A^{-1} = 1，明显 A\times B \times A^{-1}=C\times A^{-1}，利用组合意义理解一下就满足交换律 B=C\times A^{-1}。

那么已知 F，求出 G 使得 F\times G=1，考虑暴力计算：

G_S=\frac{[S=\empty] - \sum_{T \subsetneq S}G_TF_{S-T}}{F_0}

复杂度 O(3^n)，考虑分子右边的式子可以利用半在线的子集卷积处理即可，复杂度 O(2^nn^2)。

\exp

要求 F_0=0。

H=\sum_{i=1}^{n}\frac{F^i}{i!}

设 f_i 只保留 F 中大小为 i 的 S 并乘上 i，那么可得以下式子：

ig_i=\sum_{j=1}^{i} f_jg_{i-j}

用子集卷积做。复杂度 O(2^nn^2)。

\ln

要求 G_0=1。

$g=\exp(f),f=\ln(g)$，考虑 $\exp$ 的式子，可以转化为： $$ig_i=f_ig_0 \sum_{j=1}^{i-1}f_jg_{i-j}$$ $$f_i=ig_i-\sum_{j=1}^{i-1}f_jg_{i-j}$$ 用子集卷积做。复杂度 $O(2^nn^2)$。 ### 多项式复合集合幂级数 对于子集卷积，$\exp,\ln$ 都属于复合，统一表示即为 $F=\sum_{i=0}^n f^ih_i$。 如何挨个计算 $f^i$ 复杂度 $O(2^nn^3)$。可以设 $H_i=H_{i-1}\times f+h_{n-i}$，不过这样复杂度还是不变，考虑让 $f$ 的加入顺序为按照 $\max{S}$ 从小到大加入，此时 $h_i$ 变为 $i!h_i$，那么 $H_i$ 的大小就是 $2^i$，进行卷积的时候考虑枚举 $f$ 的 $max{S}$ 卷即可。复杂度 $O(\sum_{i=1}^n 2^ii^2)=O(2^nn^2)$。 所以搞了半天你告诉我 $\ln,\exp$ 直接用复合做就好了。但是直接用子集卷积做 $\ln,\exp$ 比用复合的方式做常数更小。复合常数是大约是卷积的 $1.5\sim 2$ 倍。 ### $\exp,\ln$ 组合意义 $\exp$ 可以理解为对 $S$ 进行划分成 $S_1,\ldots,S_k$ 的权值和 $\prod_{i=1}^k f_{S_i}$。$\ln$ 就是反过来？ ## 连通问题 以下问题都是： > 给定一个无向图，对于每个子图，求有多少种选边(子图内的边)方案使得该子图是“?”。 ### 连通图 设答案为 $f$。对于一个任意的选边方案，可以产生若干连通块，选边方案总数为 $g_S=2^{ed(S)}$，知道 $g=\exp f$，那么 $f=\ln g$，求出即可。 ### 连通二分图 设答案为 $f$，考虑对 $S$ 中的点黑白染色，那么染色方案为 $2^{连通块数量}$，求出 $S$ 的所有连边的黑白染色方案和，即 $g_S=\sum_{T\subsetneq S}2^{ed(S)-ed(T)-ed(S-T)}$，子集卷积即可，那么 $g=\exp f$，$f=\ln g$。 ### 树 考虑每次加入一个点，设 $f_i$ 是加入了前 $i$ 个点的连通块 $S$ 的方案数，考虑如何计算 $f_i$，如果 $S$ 本身就和 $i$ 不连通直接转移，否则将 $i$ 连接的若干连通块合并。如下： - $g_S=f_{i-1,S}\times ed(i, S)$。 - $f_i=f_{i-1}+\exp(g_S) \times \{i\}$。 复杂度 $O(2^nn^2)$。 ### 仙人掌 仙人掌可以理解为若干环的合并，一条割边也可以看作一条环。那么需要将这些环合并，找交界点即可，从 $1\ldots n$ 枚举即可，用 $\exp$ 合并，复杂度 $O(2^nn^3)$。 ## 有向图 ### DAG 定向 > 对一个子图的所有边定向，使得是 DAG 的方案数。 考虑每次删掉入度为 $0$ 的点，但是如果一次没删干净那么就会算重，考虑容斥，如果删除 $T$，系数为 $(-1)^{|T|+1}$。发现可以用复合做，$H_i=1$，复杂度 $O(2^nn^2)$。 ### 强连通子图 > 给定一个有向图，对于每个子图，求有多少种选边(子图内的边)方案使得该子图是强连通图。 设答案为 $f$。如果这不是一个强连通图，可以删除入度为 $0$ 的强连通块，设 $k=-f$，$g=-\exp k$，那么 $f_S=2^{ed(S)}-\sum_{T\subsetneq S}g_S2^{cross(T,S-T)+ed(T)}$，但 $cross(T,S-T)$ 很难搞成卷积形式，所以应该只能 $O(3^n)$。 ## 双连通 问题形式和无向图的类似。 ### 边双 考虑已经求出边双的方案，如何求连通，即“边双-连通 变换”。 设 $p_i$ 为有割边相连的点的最大值不超过 $i$，那么 $p_0$ 就是边双的方案。那么从 $p_i$ 推到 $p_{i+1}$ 只需要加入这些割边即可： - $q_{i,S}=[i\not \in S]p_{i,S} cof(i, S\cap \{1,\ldots,i-1\})$。 - 如果 $i\not \in S$，$(p_{i+1})_S=(p_i)_S$，否则 $(p_{i+1})_S=(p_i \times \exp(q_i))_S$。 反推就是“连通-边双 变换”，如果知道 $p_{i+1}$ 那么可以知道 $q_i$，直接子集卷积逆即可，细节就是卷的时候 $p_i,p_{i+1}$ 都应该是不带 $i\not \in S$ 的 $S$。复杂度 $O(2^nn^3)$。 ### 点双 和边双类似。 ## 最优化问题 给一个有向/无向图，求出有至少选多少条边使得这是一个边双/点双/强连通块。 和上文没啥关系，注意到这三种都可以耳分解解决，所以直接耳分解就没了，复杂度 $O(2^nnm)$。