集合幂级数
https://www.cnblogs.com/birchtree/p/14531986.html
https://www.luogu.me/article/vx00cltm
https://www.luogu.me/article/1p22g6n4
以下定义 \(z^S\cdot z^T=[S\cap T=\varnothing]z^{S\cup T}\)（无交并）。于是集合幂级数的乘法就定义为子集卷积。子集卷积显然具有交换律、结合律、分配律和线性性，其单位元为 \(z^{\varnothing}\)。如果 \([z^{\varnothing}]F\ne 0\)，那么其有唯一逆元。
集合无交并在图上具有良好的组合意义，因此可以解决许多图论计数问题。
全家桶
子集卷积
暴力卷积是 \(O(3^n)\) 的。先按 \(\operatorname{popcount}\) 分类，每行 \(fwt\)，每列卷积，再 \(ifwt\) 回去，正确性显然。复杂度 \(O(n^22^n)\)。
求逆
显然有递推式（边界省略）
暴力实现仍然是 \(O(3^n)\) 的，把子集卷积的卷积换成求逆即可，正确性显然。复杂度 \(O(n^22^n)\)。
exp
集合幂级数 \(F(z)\) 的 \(\exp\) 定义为
显然在 \([z^{\varnothing}]F=0\) 时收敛。其有组合意义：\([z^S]\exp(F)\) 表示 \(S\) 的全体无序划分的权值和。显然有递推式（边界省略）
对着递推式可以做到 \(O(3^n)\)，把子集卷积的卷积换成 \(\exp\) 即可，正确性也比较显然。复杂度 \(O(n^22^n)\)。
ln
集合幂级数 \(F(z)\) 的 \(\ln\) 定义为
或者递推式
显然在 \([z^{\varnothing}]F=1\) 时收敛。其有组合意义：\([z^S]\ln(F)\) 表示集合 \(S\) 不能继续分割的方案数，也可以按 \(\exp\) 的逆运算来理解。
对着递推式可以做到 \(O(3^n)\)，其实也是求解连通子图数量的朴素做法。把子集卷积的卷积换成 \(\ln\) 即可，正确性也比较显然。复杂度 \(O(n^22^n)\)。
论正确性
只需要说明所有贡献到 \(g_S\) 的部分都被统计到了即可，由于初等函数都能写成收敛的幂级数，其中集合幂级数乘法时 \(\operatorname{popcount}\) 做加法，恰好可以看成是形式幂级数的 \(x\) 的指数。又因为只有 \(\operatorname{popcount}\) 恰好等于行编号的部分才有贡献。所以集合幂级数初等函数用上面的普遍方法应当都是对的。
染色问题
给定一个图，求它的 \(k\) 染色数量。令集合幂级数 \(F(z)=\sum_{S}[S是独立集]z^S\)。答案就是 \([z^U]F^k(z)\)。先 \(\ln\) 一遍，乘 \(k\)，再 \(\exp\) 回去即可。复杂度 \(O(n^22^n)\)。
边双连通-连通 变换，逐点迭代
有集合幂级数 \(F(z)\)，边双连通-连通变换 \([z^S]trans(F,c)\) 表示 \(S\) 被划分成一些集合，用一些割边把这些部分连接起来的权值和，每条割边有 \(c\) 的权值。通过 \(trans\) 我们可以解决边双连通分量计数、生成树计数等一系列问题。
求解 \(trans(F)\) 的一般方法是逐点迭代。考虑枚举 \(i:0\sim n-1\)，每次加入 \(\max(u,v)=i\) 的割边 \((u,v)\)：
时间复杂度 \(O(n^32^n)\)。如果取 \(c=-1\)，那么每条割边将具有 \(-1\) 的容斥系数，此时如果子图 \((S,E')\) 具有割边，那么删掉或加入编号最小的割边，容斥系数抵消，因此将会统计 \(S\) 的边双分量数量。