我觉得这个东西应该叫SPS Subset Power Series吧……管他的。
这一篇经过了改造，如果你很多年后再来看发现和以前不一样了，那就是改造的成果（
约定
集合幂级数可以看成次数膜\(2\)的多元多项式。
半半在线说的是按照集合大小从小到大给出系数(也就是一次给一整个大小)，全半在线说的是按照数值从小到大给出系数。一般情况下半半在线已经足够，但是全半在线也有其用处。
集合占位幂级数
对于一个集合幂级数\(F(x)\)，它的集合占位幂级数\(P(F)\)定义为 : 把它的每一项\(f_Sx^S\)换成一个多项式\(P(f)_S(z)=f_Sx^Sz^{\vert S\vert}\)，换句话说加一个形式变量\(z\)来记录大小。以下说到占位幂级数，指的就是集合占位幂级数。
kdw问我集合幂级数是啥，就是每一项是\(a_Sx^S\)这样的。
容易发现集合占位幂级数并卷积之后取所有\(x^Sz^{\vert S\vert}\)项就对应子集卷积，解释一下就是利用大小判断是不是不交并。
具体一点，我们把加法换成多项式加法做一遍法嘛塔，然后把乘法换成爆力多项式乘法做一遍点乘，然后做一遍逆法嘛塔。复杂度\(O(2^nn^2)\)。呃为什么不用法法塔做多项式乘法?因为瓶颈不在这里，法嘛塔已经是这个复杂度了。
kdw问我子集卷积是啥(好像没问啊?)，就是不交并卷积。
一个半半在线的做法是，我们改成外层多项式卷积，内层法嘛塔并卷积。需要先全都进行一遍法嘛塔，然后用点值算，算完全都逆法嘛塔，复杂度是一样的。
让我们考虑一些集合幂操作
都是在子集卷积意义下。
\(\mathrm{inv}\)的意义显然。
\(\exp\)的组合意义还是很好解释。也就是每个集合\(S\)有\([x^S]F\)种染色方案，\([x^S](\exp F)\)就是选取若干不相交集合无序地组成\(S\)并染色的方案数。\(\ln\)当然是这个的逆过程。
vfk的古老做法
计算这几个很好说，我们把子集卷积里面的乘法换成\(\mathrm{inv},\exp,\ln\)就好了。为什么是对的?对于\(\mathrm{inv}\)是显然的。对于\(\ln,\exp\)，可以拆开它们的式子，然后从 法嘛塔是线性变换 这个事实出发感性理解。
呃注意这里复杂度瓶颈并不在多项式\(\mathrm{inv},\exp,\ln\)上，因为法嘛塔已经是\(O(2^nn^2)\)的了。可以使用常数更小的暴力算法，其中\(\mathrm{inv}\)的暴力(硬递推)已经广为人知，\(\ln\)可以通过\(\mathrm{inv}\)解决，也和\(\exp\)一样可以求导得到系数的递推式。
ei的新做法
另一个算\(\exp\)的做法是，我们把所有的子集分成\(n\)组，每一组包含\(\mathrm{highbit}\)为\(i\)的，然后拼起来的时候每一组只可能选一个，于是把这些组从小到大子集卷积起来，复杂度居然就是对的了。这个做法是半半在线的，并且不需要实现\(n^2\exp\)。
那么怎么算\(\ln\)?往下看。
多项式复合集合幂级数
也就是求\(F(G)\)，其中\(F\)是多项式，\(G\)是集合幂级数，乘法是子集卷积。
注意到一个事情，如果\([x^\varnothing]G=0\)，也就是不能选空集，那么多项式次数超过\(n\)的部分都是没有用的，一般我们只考虑这样的复合。否则多项式必须是有限的。
为了算这个复合，我们只需要算出\(G^0,G^1,...,G^n\)。考虑还是按照\(\mathrm{highbit}\)分组，拼起来的时候每一组只能选一个，但是这里我们需要额外记录可以选多少，做一个类似于dp的东西，复杂度是\(\sum\limits_i 2^ii^2(n-i)=O(2^nn^2)\)。
例题
xx open cup gp of Zhejiang F. Fast as Ryser
给简单图和常数\(c\)，定义一个大小为\(k\)的匹配权值是\(c^k\)，求所有匹配权值和。\(n\leq 36\)，可以加强到\(n\leq 40\)。
这里没法用点独立集的做法，因为边数太**多了，直接上复杂度又不是很好。
300iq看到这题时，认为它是2020年最棒的题。我们干一件非常妙的事情 : 往\(2i-1\)和\(2i\)之间连边。每一条这样的边连接的点，我们称为一个 点对。
你发现匹配加上这样的边，会变成若干不交的环和链。
然后考虑我们对于每个对的集合计算它里面构成一条链或者一个环的方案数，然后做一个子集\(\exp\)。
怎么算这个呢?考虑状压dp。
对于一条链，我们设\(dp(S,i)\)表示\(S\)中的点构成一条链，最后一个点是\(i\)的方案数，那么转移显然，复杂度是\(O(2^\frac{n}{2}n^2)\)。
对于一个环，直接跟链一样做就行了，不过我们需要记录起点，这个可以钦点编号最小的是起点，。
然后就做完了。复杂度\(O(2^\frac{n}{2}n^2)\)。
这看起来是某种经典的折半。但是是不是只对匹配有效啊（
未知来源题
图，边有边权，求所有匹配的边权乘积之和。\(n\leq 40\)。
看起来一样做。
uoj goodbye xinchou D. 马超战潼关
看起来是二分图最小割计数。
最小割等于最大匹配。
考虑对于每一条匹配边\(u\rightarrow v\)，\(s\rightarrow u,u\rightarrow v,v\rightarrow t\)必然割且仅割一条。所以我们割一下然后看是不是真的割了，复杂度是\(O(3^nm)\)。
然后呢?
给简单图，求有多少个欧拉生成子图。生成子图指的是选一些边，把它们的端点也拿出来的子图。\(n\leq 20\)，6s。
呃考虑我们可以先搞定度数都为偶数的子图，然后做一个子集\(\ln\)去掉不连通的情况。
这个怎么求?很简单，我们发现全都是偶数相当于一些异或方程，也就是每条边会给它的端点分别异或\(1\)，我们要求最后每个点都是\(0\)。
呃异或方程组解计数咋做啊?把所有点的状态压成一个数，边也压成一个数，这样就是求异或起来得到\(0\)的方案数，可以用线性基\(O(nm)\)解决。复杂度\(O(2^n(n+m^2))\)，不过常数好像不大。
增量法计算sps被称为 逐点牛顿迭代法。
给简单图，求有多少个点双连通生成子图。\(n\leq 20\)，10s。
点双连通，就是连通并且没有割点。
连通很好搞，我们直接对生成子图的SPS取\(\ln\)就得到连通子图的SPS。
然后考虑枚举一个割点，对于每个有割点的生成子图，在编号最小的割点处把它干掉。换句话说我们依次加入每个点，通过 \(\leq i-1\)的点不是割点的生成子图的SPS \(F_{i-1}\) 计算 \(\leq i\)的点不是割点的生成子图的SPS \(F_i\)。
呃这个咋做?考虑我们要求在某个生成子图中，一个点是割点，就相当于把这个点删去之后，这个生成子图会变成多于一个的生成子图。而变出来的这些生成子图已经被\(F_{i-1}\)都数出来了，所以用\(F_{i-1}\)算出\(F_i\)应该是可行的。
然后就很好玩了，我们找到所有包含\(i\)的项，把它们里面删去\(i\)(就是贡献到\(S-i\))之后单独拿出来做一个\(\ln\)进行分解。这样做的正确性在于，如果一个生成子图删掉\(i\)变成了多个生成子图，这些变出来的生成子图也会因为删去\(i\)被生成出来。最后把\(\ln\)之后的部分拍回去即可(呃是不是应该说替换回去?)。这样做的复杂度是\(O(2^nn^3)\)。
有一个常数优化 : 你发现我们每次都是在法嘛塔之后的数组上做\(\ln\)，所以实际上没必要每次重新法嘛塔，可以一开始就法嘛塔一遍。然后要做一部分的\(\ln\)的时候，你发现恰好可以简单地减去没有影响的部分。这样复杂度瓶颈就是多项式\(\ln\)了，可以改成法法塔优化到\(O(2^nn^2\log n)\)，不过那显然不会快多少。
给简单图，求有多少个边双连通生成子图。\(n\leq 20\)，10s。
要用基于点的集合幂级数处理边有些难度，不过你发现边双跟点双存在某种关系。具体地，你发现割边对应大小为\(2\)的点双(也就是两个点之间连一条边)，所以如果一张连通图不包含大小为\(2\)的点双(当然是极大的)，那么它边双连通。
先跑一遍点双连通生成子图，然后我们去掉所有集合大小为\(2\)的项(把它们置为\(0\))，然后倒着做上面的过程，也就是把\(\ln\)换成\(\exp\)。这样就可以在连通图中减去包含大小为\(2\)的点双的部分。
loj6719 300iq Contest 2 数仙人掌 加强版
给简单图，求有多少个仙人掌生成子图。\(n\leq 18\)，7.5s。
考虑一个性质 : 仙人掌是若干环的并，这里认为两个点连一条边也是环。这有什么用?
接起来就很像\(\exp\)。考虑如果求出了环的集合幂级数，说不定可以搞出仙人掌的集合幂级数。
咋搞?我们先枚举一个点\(i\)作为环的交点。把所有包含这个点的仙人掌拿出来(它们上面的环目前只可能交于前\(i-1\)个点)，然后全部挖掉\(i\)并做一个\(\exp\)，最后再把\(i\)塞回去，然后把我们得到的新的仙人掌加到原来的集合幂级数上去。这就做完了。
现在问题是怎么求环的集合幂级数。你发现这个在Fast as Ryser里做过了（
无根树计数
给简单图，定义一棵生成树的权值是边权的积，两棵生成树不同当且仅当边集不同。对于每个点集的非空子集，求它的所有生成树的权值和。\(n\leq 20\)。
呃还是(这才是论文例题吧?)逐点牛迭，我们考虑生成树显然很有子结构，所以\(\exp\)一下拼就是了。感觉这个完全弱于 仙人掌生成子图计数。
gym103202m
wc2018 州区划分
考虑这个权值说的是啥。容易想到因为每个划分可以任意排列，我们可以把划分变成无序的(集合幂也是在处理这样的东西)，然后对所有\(k!\)种方案求和。看起来它是
\[\left(\prod_{i=1}^{k}s_i^p\right)\sum_{f}\prod_{i=1}^k\frac{1}{\sum_{j=1}^i s_j^p}\]。注意到\(p\leq 2\)，首先我们判定每个子集是不是合法的，然后如果\(p=0\)那么我们直接子集exp，如果\(p=1\)，我们可以看看它是个啥，我看不出来，不过据说它总是\(1\)
如果\(p=2\)，看起来上面的结论不是很能成立了。我们可以写一个朴素的dp，看起来是
\[dp(S)=\sum_{T\subseteq S}\left(\frac{s_T}{s_S}\right)^p dp(S-T)=\frac{1}{s_S^p}\sum_{T\subseteq S,T\neq\varnothing}s_T^p dp(S-T)\]然后我们做一个半半在线卷积就好了。