专栏文章

集合幂计数

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mip83mz6
此快照首次捕获于
2025/12/03 07:42
3 个月前
此快照最后确认于
2025/12/03 07:42
3 个月前
查看原文
以下均为无向图，对不同形态的边子图计数。带大家从头到尾玩一遍。
你问我逐点迭代是什么？把集合幂级数看成 nn 元多项式，截断到每元都只考虑到一次项。然后你考虑一下 ∂∂xnF\dfrac{\partial}{\partial x_n}F 和 FF 的关系即可。算两次哈哈哈。

0. 数子图

热身题。答案显然是 2边数2^{边数}。复杂度 O(2n)O(2^n)。

1. 数连通子图

注意到连通的 exp 是任意，因此把问题 1 得到的集合幂级数求个 ln 即可。复杂度 O(n22n)O(n^22^n)。

2. 数（无根）生成树

逐点迭代法。每次加一个最大点，对不超过它的那些部分做次 exp。复杂度是 ∑i<ni22i=O(n22n)\sum\limits_{i<n}i^22^i=O(n^22^n)。

3. 数森林

对问题 3 做一次 exp，复杂度 O(n22n)O(n^22^n)。

4. 数链

随便找一个点作为开头然后 dp，别忘了长度 >1>1 时要 /2/2。状态数 O(n2n)O(n2^n)，转移 O(n)O(n)，总复杂度 O(n22n)O(n^22^n)。

5. 数环

要固定一个环上最大的点开始 dp，和链几乎相同，最后也别忘了 /2/2，总复杂度 O(n22n)O(n^22^n)。

练习 1：数固定起终点的杏仁

先用问题 4 得到杏仁的一条路的方案数，再 exp 一下即可。

6. 数连通欧拉图

大致等价于每个点度数都是偶数。但是会有问题就是不连通，如果不限制连通性能做的话，把其求个 ln 就好了。接下来考虑如何计数每个点度数都是偶数的边子图数量。
对每条边选/不选设置一个权值 0/10/1，则要求所有点的所有邻边权值的 xor 为 00。等价于，一个 n×mn\times m 的 F2\mathbb{F}_2 意义下的矩阵的解空间大小，一定是 2rank2^{rank}。将矩阵转置，得出 rankrank 就是连通块数量，容易 O(n22n)O(n^22^n) 预处理出来。总复杂度一样。

7. 数边仙人掌/沙漠

要开始在刻画上面上难度了。注意到边仙人掌等价于每个点双是单点，一条边，或者是一个环。可以先用问题 5 得到一个集合 SS 可以作为点双的方案数 dpSdp_{S}。
问题变成：对所有边子图，对其所有点双的方案数的乘积求和。这就是一个标准的点双连通-连通变换。
做法是设一个集合幂级数列 Fi(x)F_i(x) 表示所有割点都 ≤i\leq i 的贡献和。每次加一个割点做一次 exp 即可。数沙漠就是对刚才这个问题 exp 一下。
时间复杂度 O(2nn3)O(2^nn^3)。

8. 数点仙人掌

和问题 7 比较类似，不过刻画方法是每个 边双 都是单点或环，用问题 5 得到每个集合 SS 作为边双的方案数 dpSdp_S。
接下来考虑对其做边双连通-连通变换：
设集合幂级数列 Fi(x)F_i(x) 表示所有割边的两个端点均不超过 ii 的方案数。每次加一个割边的端点 ii，也是做一次 exp，还要对包含 ii 的集合做个子集卷积就得到了答案。点仙人掌沙漠也同理是对刚才这个 exp 一下。
时间复杂度 O(2nn3)O(2^nn^3)。

9. 数点双/边双连通子图

刚才已经介绍了点/边双连通-连通变换，接下来讲下它的逆变换，也就是连通-点/边双连通变换。
点双逆回来时很容易的。因为只有一次 exp，自然 ln 回来即可。
边双乍一看没法做（如果你不和我一样唐就当我没说这句话），但你仔细想下，exp 的部分并没改变过，所以可以直接 exp 倒数算出来，乘回去就好了。
回到原题，如果分别把点/边双的贡献设为 11，做点/边双连通-连通变换，则得到的答案就是连通图的数量，也就是问题 1。因此先把这个求出来，用逆变换反着算回去即可。
时间复杂度 O(2nn3)O(2^nn^3)。

10. 数匹配

原题数据范围很奇怪，n≤36n\leq 36。接下类一个很神奇的转化，我无法理解怎么想到的：
考虑如何刻画匹配。一个有点困难，自由度有点高，不如先固定另一个匹配，把这两个匹配叠起来。一个边子图是匹配当且仅当每个点度数 ≤1\leq 1，则两个匹配拼起来的图当然满足每个点度数 ≤2\leq 2，这代表每个连通块都是链或者是环。
那怎么找固定匹配呢？其实最好要求每个点都要出现在匹配中，这样很多对点就被“捆绑”起来了！因此，先不妨设 nn 是偶数，再取一个匹配（边不需要在原图中）：(1,2),(3,4),…,(n−1,n)(1,2),(3,4),\dots,(n-1,n)。
这时，你再关注每个连通块。不难发现，大小一定是偶数，因为固定匹配的匹配点一定成对出现。于是集合只有 2k2^k 种情况，其中 k=n/2k=n/2。
那这里链和环的方案数其实是分别和问题 4,5 是类似的，也可以 O(k22k)O(k^22^k) dp 出来。
分别设链和环对应的集合幂级数为 FF 和 GG。则答案是 [x2k−1]exp⁡(F+G)[x^{2^k-1}]\exp(F+G)。
总复杂度 O(n22n2)O(n^22^{\frac{n}{2}})。

11. 数固定大小匹配

按刚才那个做法直接做是 O(k32k)O(k^32^k) 的。
首先有个弱化版 Fast as Ryser，给了个常数 cc，让你求的是对所有匹配 E′E'，c∣E′∣c^{|E'|} 的和。这里你可以注意到的是，匹配大小就等于 kk 减掉链连通块个数。因此答案是 ck[x2k−1]exp⁡(F/c+G)c^{k}[x^{2^k-1}]\exp(F/c+G)。
如果不固定大小 cc，

评论

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

正在加载评论...