从分治乘法到快速沃尔什变换及其反演

为了方便本文的叙述，先定义如下内容：

设$a$，$b$为两个序列，那么：

$(a,b)$表示将$a$和$b$简单地拼接在一起组成的序列。

设$f$是一个$n$维集合幂级数（$n>0$），那么：

$f^{-}$表示取所有下标的最高位为$0$的项，并忽略最高位而组成的一个$n-1$维集合幂级数（其实就是$f$的前半段）。

类似的，$f^{+}$表示取所有下标的最高位为$1$的项，并忽略最高位而组成的一个$n-1$维集合幂级数。（其实就是$f$的后半段）。

用$\cdot$代表点积，其形式为：

$$(f\cdot g{)}_i=f_i\cdot g_i$$

用$\ast$代表卷积，其形式为：

$$(f\ast g{)}_i=\sum _{j\circ k=i}{f}_j\cdot g_k$$

其中下标运算$\circ$会在上下文给出（或者是普遍情况，不做要求）。

我们先考虑如何用分治乘法解决常见的集合幂级数的卷积。

我们考虑将待卷积的集合幂级数$f$和$g$拆分成$(f^{-},f^{+})$和$(g^{-},g^{+})$，那么：

$$f\ast g=(f^{-},f^{+})\ast (g^{-},g^{+})$$

显然我们可以选择一种位运算，根据这种位运算将$f^{-}\ast g^{-}$，$f^{-}\ast g^{+}$，$f^{+}\ast g^{-}$，$f^{+}\ast g^{+}$的贡献计算给$(f\ast g{)}^{-}$和$(f\ast g{)}^{+}$中的某一个。

对于集合并卷积，计算贡献的式子就是：

$$f\ast g=(f^{-}\ast g^{-},f^{-}\ast g^{+}+f^{+}\ast g^{-}+f^{+}\ast g^{+})$$

显然四个新的卷积可以直接递归计算，那么递归式便为：

$$T(n)=4T(n-1)+O(2^n)$$

解得$T(n)=O(4^n)$，直接做并没有什么用。我们来考虑减少递归的次数，我们发现：

$$f^{-}\ast g^{+}+f^{+}\ast g^{-}+f^{+}\ast g^{+}=(f^{-}\ast g^{+}+f^{+}\ast g^{-}+f^{+}\ast g^{+})+f^{-}\ast g^{-}-f^{-}\ast g^{-}$$

显然等式右边的前四项是可以合并的，也就是：

$f^{-}\ast g^{+}+f^{+}\ast g^{-}+f^{+}\ast g^{+}=(f^{-}+f^{+})\ast (g^{-}+g^{+})-f^{-}\ast g^{-}$

后面一项之前已经计算过，可以重复利用，只要多算一项即可。因此递归式为：

$$T(n)=2T(n-1)+O(2^n)$$

解得$T(n)=O(2^{n}n)$，复杂度非常优秀。

现在我们来尝试从分治乘法推出其快速沃尔什变换的形式。

考虑之前推出的式子，我们对于集合幂级数$f$，我们只需要保留$f^{-}$和$f^{-}+f^{+}$即可直接递归计算其集合并卷积。那么我们不妨先定义一个变换$f^{\prime }=(f^{-},f^{-}+f^{+})$。

研究一下$(f\ast g{)}^{\prime }$的性质，得到：

$$(f\ast g{)}^{\prime }=(f^{-}\ast g^{-},(f^{-}+f^{+})\ast (g^{-}+g^{+}))$$

这个式子也等价于：

$$(f\ast g{)}^{\prime -}=f^{\prime -}\ast g^{\prime -}，(f\ast g{)}^{\prime +}=f^{\prime +}\ast g^{\prime +}$$

我们发现做了这个变换以后，集合幂级数的前半段和后半段就没有什么关系了，可以直接分开计算。那么我们不难发现如果我们对第二维也做这样的变换，我们可以分成四段进行计算。以此类推，如果对$n$维都做这样的变换的话，计算就分开成了$2^n$个独立的部分，可以直接用点积来计算。

因此得到集合并卷积的快速沃尔什变换：

$$FWT(f)=(FWT(f^{-}),FWT(f^{-})+FWT(f^{+}))$$

剩下的一个问题就是做过快速沃尔什变换的$f$和$g$的点积是$f\ast g$快速沃尔什变换后的形式，因此我们还需要考虑其逆变换。

对于一维的变换，不难发现：

$$f=(f^{\prime -},-f^{\prime -}+f^{\prime +})$$

代入证明即可。类似的，我们将这个变换应用于$n$维，得到：

$$FW{T}^{-1}(f)=(FW{T}^{-1}(f^{-}),-FW{T}^{-1}(f^{-})+FW{T}^{-1}(f^{+}))$$

集合交卷积显然是类似的，为了完整我们也来推一遍：

$$f\ast g=(f^{-}\ast g^{-}+f^{-}\ast g^{+}+f^{+}\ast g^{-},f^{+}\ast g^{+})$$

转化为两次乘法：

$$f\ast g=((f^{-}+f^{+})\ast (g^{-}+g^{+})-f^{+}\ast g^{+},f^{+}\ast g^{+})$$

类似的得到变换$f^{\prime }=(f^{-}+f^{+},f^{+})$，复合得：

$$FWT(f)=(FWT(f^{-})+FWT(f^{+}),FWT(f^{+}))$$

类似的得到其逆变换：

$$FW{T}^{-1}(f)=(FW{T}^{-1}(f^{-})-FW{T}^{-1}(f^{+}),FW{T}^{-1}(f^{+}))$$

下面介绍集合对称差卷积。根据对称差的定义，有：

$$f\ast g=(f^{-}\ast g^{-}+f^{+}\ast g^{+},f^{-}\ast g^{+}+f^{+}\ast g^{-})$$

对于这个形式找只计算两次乘法的形式我觉得其实挺要脑力的，不过还是可以找出来的，即：

$$f\ast g=(\frac{(f^{-}+f^{+})\ast (g^{-}+g^{+})+(f^{-}-f^{+})\ast (g^{-}-g^{+})}{2},\frac{(f^{-}+f^{+})\ast (g^{-}+g^{+})-(f^{-}-f^{+})\ast (g^{-}-g^{+})}{2})$$

因此对于集合幂级数$f$我们只需要知道$f^{-}+f^{+}$和$f^{-}-f^{+}$，构造变换$f^{\prime }=(f^{-}+f^{+},f^{-}-f^{+})$，同样可以将卷积分为前后两部分，因此复合这个变换得到集合对称差卷积的快速沃尔什变换：

$$FWT(f)=(FWT(f^{-})+FWT(f^{+}),FWT(f^{-})-FWT(f^{+}))$$

同时得出其逆变换：

$$FW{T}^{-1}(f)=(\frac{FW{T}^{-1}(f^{-})+FW{T}^{-1}(f^{+})}{2},\frac{FW{T}^{-1}(f^{-})-FW{T}^{-1}(f^{+})}{2})$$

同时可以发现集合对称差卷积要求值域有$2$的逆元。

$2019.1.1\mathrm{u}\mathrm{p}\mathrm{d}$：这篇文章写了有段时间了，之后我似乎想到了一个更简洁的解释快速沃尔什变换的方法：将逻辑或看作取$max$，那么集合并卷积就是对每一维做$max$卷积。可以推得$max$卷积的卷积变换就是前缀和，逆变换就是差分。于是只要利用卷积的复合，对每一维做前缀和以及变换完之后的差分即可。集合交卷积也是相似的。至于集合对称差卷积，由于逻辑异或可以看作是模$2$意义下的加法，于是只要对每一维做长度为$2$的循环卷积即可。