专栏文章

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

llarsr
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip6vorr
此快照首次捕获于
2025/12/03 07:08
3 个月前
此快照最后确认于
2025/12/03 07:08
3 个月前
查看原文
参考 cxy APIO 课件和 lgx 不知道从哪里搞来的什么课件，还有网上的众多博客。

集合幂级数

通俗讲就是状压。
可以用 FWT 进行一些简单运算，比如 OR/XOR/AND 卷积。

子集卷积

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

子集卷积逆

要求 A0=1,C0=1A_0=1,C_0=1。
已知 A×B=CA\times B=C 和 A,CA,C，求 BB。设 A−1A^{-1} 使得 A×A−1=1A\times A^{-1} = 1，明显 A×B×A−1=C×A−1A\times B \times A^{-1}=C\times A^{-1}，利用组合意义理解一下就满足交换律 B=C×A−1B=C\times A^{-1}。
那么已知 FF，求出 GG 使得 F×G=1F\times G=1，考虑暴力计算： GS=[S=∅]−∑T⊊SGTFS−TF0G_S=\frac{[S=\empty] - \sum_{T \subsetneq S}G_TF_{S-T}}{F_0}
复杂度 O(3n)O(3^n)，考虑分子右边的式子可以利用半在线的子集卷积处理即可，复杂度 O(2nn2)O(2^nn^2)。

exp⁡\exp

要求 F0=0F_0=0。
H=∑i=1nFii!H=\sum_{i=1}^{n}\frac{F^i}{i!} 设 fif_i 只保留 FF 中大小为 ii 的 SS 并乘上 ii，那么可得以下式子：
igi=∑j=1ifjgi−jig_i=\sum_{j=1}^{i} f_jg_{i-j}
用子集卷积做。复杂度 O(2nn2)O(2^nn^2)。

ln⁡\ln

要求 G0=1G_0=1。
ln⁡\ln 为 exp⁡\exp 的逆。
g=exp⁡(f),f=ln⁡(g)g=\exp(f),f=\ln(g)，考虑 exp⁡\exp 的式子，可以转化为：
igi=fig0∑j=1i−1fjgi−jig_i=f_ig_0 \sum_{j=1}^{i-1}f_jg_{i-j} fi=igi−∑j=1i−1fjgi−jf_i=ig_i-\sum_{j=1}^{i-1}f_jg_{i-j}
用子集卷积做。复杂度 O(2nn2)O(2^nn^2)。

多项式复合集合幂级数

对于子集卷积，exp⁡,ln⁡\exp,\ln 都属于复合，统一表示即为 F=∑i=0nfihiF=\sum_{i=0}^n f^ih_i。
如何挨个计算 fif^i 复杂度 O(2nn3)O(2^nn^3)。可以设 Hi=Hi−1×f+hn−iH_i=H_{i-1}\times f+h_{n-i}，不过这样复杂度还是不变，考虑让 ff 的加入顺序为按照 max⁡S\max{S} 从小到大加入，此时 hih_i 变为 i!hii!h_i，那么 HiH_i 的大小就是 2i2^i，进行卷积的时候考虑枚举 ff 的 maxSmax{S} 卷即可。复杂度 O(∑i=1n2ii2)=O(2nn2)O(\sum_{i=1}^n 2^ii^2)=O(2^nn^2)。
所以搞了半天你告诉我 ln⁡,exp⁡\ln,\exp 直接用复合做就好了。但是直接用子集卷积做 ln⁡,exp⁡\ln,\exp 比用复合的方式做常数更小。复合常数是大约是卷积的 1.5∼21.5\sim 2 倍。

exp⁡,ln⁡\exp,\ln 组合意义

exp⁡\exp 可以理解为对 SS 进行划分成 S1,…,SkS_1,\ldots,S_k 的权值和 ∏i=1kfSi\prod_{i=1}^k f_{S_i}。ln⁡\ln 就是反过来？

连通问题

以下问题都是：
给定一个无向图，对于每个子图，求有多少种选边(子图内的边)方案使得该子图是“?”。

连通图

设答案为 ff。对于一个任意的选边方案，可以产生若干连通块，选边方案总数为 gS=2ed(S)g_S=2^{ed(S)}，知道 g=exp⁡fg=\exp f，那么 f=ln⁡gf=\ln g，求出即可。

连通二分图

设答案为 ff，考虑对 SS 中的点黑白染色，那么染色方案为 2连通块数量2^{连通块数量}，求出 SS 的所有连边的黑白染色方案和，即 gS=∑T⊊S2ed(S)−ed(T)−ed(S−T)g_S=\sum_{T\subsetneq S}2^{ed(S)-ed(T)-ed(S-T)}，子集卷积即可，那么 g=exp⁡fg=\exp f，f=ln⁡gf=\ln g。

树

考虑每次加入一个点，设 fif_i 是加入了前 ii 个点的连通块 SS 的方案数，考虑如何计算 fif_i，如果 SS 本身就和 ii 不连通直接转移，否则将 ii 连接的若干连通块合并。如下：
  • gS=fi−1,S×ed(i,S)g_S=f_{i-1,S}\times ed(i, S)。
  • fi=fi−1+exp⁡(gS)×{i}f_i=f_{i-1}+\exp(g_S) \times \{i\}。
复杂度 O(2nn2)O(2^nn^2)。

仙人掌

仙人掌可以理解为若干环的合并，一条割边也可以看作一条环。那么需要将这些环合并，找交界点即可，从 1…n1\ldots n 枚举即可，用 exp⁡\exp 合并，复杂度 O(2nn3)O(2^nn^3)。

有向图

DAG 定向

对一个子图的所有边定向，使得是 DAG 的方案数。
考虑每次删掉入度为 00 的点，但是如果一次没删干净那么就会算重，考虑容斥，如果删除 TT，系数为 (−1)∣T∣+1(-1)^{|T|+1}。发现可以用复合做，Hi=1H_i=1，复杂度 O(2nn2)O(2^nn^2)。

强连通子图

给定一个有向图，对于每个子图，求有多少种选边(子图内的边)方案使得该子图是强连通图。
设答案为 ff。如果这不是一个强连通图，可以删除入度为 00 的强连通块，设 k=−fk=-f，g=−exp⁡kg=-\exp k，那么 fS=2ed(S)−∑T⊊SgS2cross(T,S−T)+ed(T)f_S=2^{ed(S)}-\sum_{T\subsetneq S}g_S2^{cross(T,S-T)+ed(T)}，但 cross(T,S−T)cross(T,S-T) 很难搞成卷积形式，所以应该只能 O(3n)O(3^n)。

双连通

问题形式和无向图的类似。

边双

考虑已经求出边双的方案，如何求连通，即“边双-连通 变换”。
设 pip_i 为有割边相连的点的最大值不超过 ii，那么 p0p_0 就是边双的方案。那么从 pip_i 推到 pi+1p_{i+1} 只需要加入这些割边即可：
  • qi,S=[i∉S]pi,Scof(i,S∩{1,…,i−1})q_{i,S}=[i\not \in S]p_{i,S} cof(i, S\cap \{1,\ldots,i-1\})。
  • 如果 i∉Si\not \in S，(pi+1)S=(pi)S(p_{i+1})_S=(p_i)_S，否则 (pi+1)S=(pi×exp⁡(qi))S(p_{i+1})_S=(p_i \times \exp(q_i))_S。
反推就是“连通-边双 变换”，如果知道 pi+1p_{i+1} 那么可以知道 qiq_i，直接子集卷积逆即可，细节就是卷的时候 pi,pi+1p_i,p_{i+1} 都应该是不带 i∉Si\not \in S 的 SS。复杂度 O(2nn3)O(2^nn^3)。

点双

和边双类似。

最优化问题

给一个有向/无向图，求出有至少选多少条边使得这是一个边双/点双/强连通块。
和上文没啥关系，注意到这三种都可以耳分解解决，所以直接耳分解就没了，复杂度 O(2nnm)O(2^nnm)。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...