记得去年省选二试前我翻开vfk的集合幂级数论文，想要学习一波。

然而一年过去了，我发现我好像还没学。于是又是一年省选将至，我还是赶快把坑填了吧。

先定义两个主角

$$F(x) = \sum_{S \in 2 ^ U} {f_S x ^ S}$$

$$G(x) = \sum_{S \in 2 ^ U} {g_S x ^ S}$$

集合并卷积

定义$F(x)$和$G(x)$的集合并卷积$H(x)$如下

$$H(x) = \sum_{S \in 2 ^ U} \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R = S] f_L g_R x ^ S}$$

我们关注

$$h_S = \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R = S] f_L g_R}$$

这里有一个相等的限制，一般这种限制我们不容易直接解决。回忆解决这类问题的方法，不妨考虑把相等改为子集的约束，再通过容斥求答案。

根据上面的思路，不妨设

$$\begin{aligned} \hat{h}_S = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R \subseteq S] f_L g_R} \\ = & (\sum_{L \subseteq S} {f_L}) (\sum_{R \subseteq S} {g_R}) = \sum_{T \subseteq S} {h_T} \end{aligned}$$

这启发我们定义一种变换

$$\hat{h}_S = \sum_{T \subseteq S} {h_S}$$

同时由容斥原理得

$$h_S = \sum_{T \subseteq S} {(-1) ^ {|S|-|T|} \hat{h}_S}$$

此时我们发现

$$\hat{h}_S = \hat{f}_S \cdot \hat{g}_S$$

卷积转化为了点积，加速了计算。

我们知道了上面这种变换有一个优美的名字叫快速莫比乌斯变换(Fast Mobius Transform, FMT)，可以在$O(n 2 ^ n)$的时间完成一次变换或者逆变换。这无疑比暴力计算的效率高多了。

集合对称差卷积

定义$F(x)$和$G(x)$的集合对称差卷积$H(x)$如下

$$H(x) = \sum_{S \in 2 ^ U} \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R = S] f_L g_R x ^ S}$$

我们关注

$$h_S = \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R = S] f_L g_R}$$

首先考虑一个等式

$$\sum_{T \in 2 ^ U} {(-1) ^ {|S \cap T|}} = [S = \emptyset] 2 ^ n$$

代入原式化简

$$\begin{aligned} h_S = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R \oplus S = \emptyset] f_L g_R} \\ = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {\frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap (L \oplus R \oplus S)|} f_L g_R}} \\ = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {\frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap L|} (-1) ^ {|T \cap R|} (-1) ^ {|T \cap S|} f_L g_R}} \\ = & \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} (\sum_{L \in 2 ^ U} {(-1) ^ {|T \cap L|}f_L}) (\sum_{R \in 2 ^ U} {(-1) ^ {|T \cap R|} g_R})}\end{aligned}$$

令

$$\hat{h}_S = (\sum_{L \in 2 ^ U} {(-1) ^ {|S \cap L|}f_L}) (\sum_{R \in 2 ^ U} {(-1) ^ {|S \cap R|} g_R})$$

则

$$h_S = \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} \hat{h}_T}$$

大概是一个比较套路的反演？和上面类似，我们发现这里面也有一些类似的形式，启发我们定义这样的变换

$$\hat{h}_S = \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} h_T}$$

和逆变换

$$h_S = \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} \hat{h}_T}$$

此时我们发现

$$\hat{h}_S = \hat{f}_S \cdot \hat{g}_S$$

卷积又转化为了点积，又加速了计算。

我们同样知道上面这种变换也有一个优美的名字叫快速沃尔什变换(Fast Walsh Transform, FWT)，可以在$O(n 2 ^ n)$的时间完成一次变换或者逆变换。这无疑又比暴力计算的效率高多了。