集合幂计数

strapplE · 2025-05-23 19:40:37 · 算法·理论

以下均为无向图，对不同形态的边子图计数。带大家从头到尾玩一遍。

你问我逐点迭代是什么？把集合幂级数看成 n 元多项式，截断到每元都只考虑到一次项。然后你考虑一下 \dfrac{\partial}{\partial x_n}F 和 F 的关系即可。算两次哈哈哈。

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

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

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

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

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

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

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

大致等价于每个点度数都是偶数。但是会有问题就是不连通，如果不限制连通性能做的话，把其求个 ln 就好了。接下来考虑如何计数每个点度数都是偶数的边子图数量。

对每条边选/不选设置一个权值 0/1，则要求所有点的所有邻边权值的 xor 为 0。等价于，一个 n\times m 的 \mathbb{F}_2 意义下的矩阵的解空间大小，一定是 2^{rank}。将矩阵转置，得出 rank 就是连通块数量，容易 O(n^22^n) 预处理出来。总复杂度一样。

要开始在刻画上面上难度了。注意到边仙人掌等价于每个点双是单点，一条边，或者是一个环。可以先用问题 5 得到一个集合 S 可以作为点双的方案数 dp_{S}。

问题变成：对所有边子图，对其所有点双的方案数的乘积求和。这就是一个标准的点双连通-连通变换。

做法是设一个集合幂级数列 F_i(x) 表示所有割点都 \leq i 的贡献和。每次加一个割点做一次 exp 即可。数沙漠就是对刚才这个问题 exp 一下。

时间复杂度 O(2^nn^3)。

和问题 7 比较类似，不过刻画方法是每个边双都是单点或环，用问题 5 得到每个集合 S 作为边双的方案数 dp_S。

接下来考虑对其做边双连通-连通变换：

设集合幂级数列 F_i(x) 表示所有割边的两个端点均不超过 i 的方案数。每次加一个割边的端点 i，也是做一次 exp，还要对包含 i 的集合做个子集卷积就得到了答案。点仙人掌沙漠也同理是对刚才这个 exp 一下。

时间复杂度 O(2^nn^3)。

刚才已经介绍了点/边双连通-连通变换，接下来讲下它的逆变换，也就是连通-点/边双连通变换。

点双逆回来时很容易的。因为只有一次 exp，自然 ln 回来即可。

边双乍一看没法做（如果你不和我一样唐就当我没说这句话），但你仔细想下，exp 的部分并没改变过，所以可以直接 exp 倒数算出来，乘回去就好了。

回到原题，如果分别把点/边双的贡献设为 1，做点/边双连通-连通变换，则得到的答案就是连通图的数量，也就是问题 1。因此先把这个求出来，用逆变换反着算回去即可。

时间复杂度 O(2^nn^3)。

原题数据范围很奇怪，n\leq 36。接下类一个很神奇的转化，我无法理解怎么想到的：

考虑如何刻画匹配。一个有点困难，自由度有点高，不如先固定另一个匹配，把这两个匹配叠起来。一个边子图是匹配当且仅当每个点度数 \leq 1，则两个匹配拼起来的图当然满足每个点度数 \leq 2，这代表每个连通块都是链或者是环。

那怎么找固定匹配呢？其实最好要求每个点都要出现在匹配中，这样很多对点就被“捆绑”起来了！因此，先不妨设 n 是偶数，再取一个匹配（边不需要在原图中）：(1,2),(3,4),\dots,(n-1,n)。

这时，你再关注每个连通块。不难发现，大小一定是偶数，因为固定匹配的匹配点一定成对出现。于是集合只有 2^k 种情况，其中 k=n/2。

那这里链和环的方案数其实是分别和问题 4,5 是类似的，也可以 O(k^22^k) dp 出来。

分别设链和环对应的集合幂级数为 F 和 G。则答案是 [x^{2^k-1}]\exp(F+G)。

总复杂度 O(n^22^{\frac{n}{2}})。

按刚才那个做法直接做是 O(k^32^k) 的。

首先有个弱化版 Fast as Ryser，给了个常数 c，让你求的是对所有匹配 E'，c^{|E'|} 的和。这里你可以注意到的是，匹配大小就等于 k 减掉链连通块个数。因此答案是 c^{k}[x^{2^k-1}]\exp(F/c+G)。

如果不固定大小 c，