FWT(Fast Walsh Transformation)快速沃尔什变换学习笔记

引入

对于两个多项式，形如

a0×x0+a1×x1+⋯+an×xn$$a_0\times x^0+a_1\times x^1+\cdots +a_n\times x^n$$

我们将其记为f(x)$f(x)$与g(x)$g(x)$，当我们需要快速求h(x)=f(x)∗g(x)$h(x)=f(x)\ast g(x)$(卷积)时，我们就会用FFT$\mathrm{F}\mathrm{F}\mathrm{T}$算法来解决这个问题。
而FWT$\mathrm{F}\mathrm{W}\mathrm{T}$就是来解决集合上的一类卷积问题。

---

• 前言

在比赛与平时练题时，我们常常会遇到一些关于集合的动态规划的问题，比如集合的方案数计数，某些集合的权值计算等，但是一般推出的递推式复杂度会成指数或者阶乘之高，是无法忍受的，但是又没有好的解决方法，于是就放弃去打爆力算了。

---

那么对于两个集合，形如

{a0,a1,a2,…,an}$$\{a_0,a_1,a_2,\dots ,a_n\}$$

我们将其记为A$A$与B$B$，现在又两个分别定义在A$A$和B$B$的函数f$f$与g$g$，现有另一个定义在集合上的函数h$h$。对于一个集合S$S$，hS$h_S$的计算方式如下，我们用O$O$表示全集，其中A⊆O,B⊆O,S⊆O$A\subseteq O,B\subseteq O,S\subseteq O$。

hS=∑I⊆O∑J⊆O[I⨂J=S]fI×gJ$$h_S=\sum _{I\subseteq O}\sum _{J\subseteq O}[I⨂J=S]f_I\times g_J$$

这里⨂$⨂$为一类集合的运算，一般为⋃⋂⨁$\bigcup \bigcap ⨁$(交，并，对称差)，这个便是集合的卷积。

那么有没有类似FFT的方法快速计算两个集合之间的卷积呢?若有不就可以解决前言中的问题了?答案肯定是有的。

---

前置

集合幂级数

对数列理论熟悉的读者应该知道，我们可以把一个数列f0,f1,f2,…$f_0,f_1,f_2,\dots$和一个形式幂级数f(x)=∑0≤k fk×xk$f(x)=\sum _{0\le k}{f}_k\times x^k$相对应，称之为该数列的生成函数。由于有很多相关的理论与快速算法，这个方法就能解决很多的数列的计算问题。

那么我们对于集合也定义类似的东西，看看能否达到同样的效果。

设F$F$是一个域，则称函数f:O −> F$f:O->F$为F$F$上的一个集合幂级数，对于一个集合S(S⊆O)$S(S\subseteq O)$，我们令fS$f_S$为把S$S$带入函数f$f$时的函数值，同样的将fS$f_S$称为该集合幂级数的第S$S$项的系数。那么如果所有的fS$f_S$确定了的话，该函数f$f$也就确定了。

那么我们设f,g$f,g$为集合幂级数，定义加法f+g=h$f+g=h$，h$h$也是一个集合幂级数，且对于一个集合S$S$，满足如下式子:

hS=fS+gS$$h_S=f_S+g_S$$

所以，集合幂级数的加法就是对应系数相加，减法同理，改为fS−gS$f_S-g_S$即可。

下面我们定义集合幂级数的具体形式。参照形式幂级数的样子，我们定义如下: 对于任意的v∈F,S⊆O$v\in F,S\subseteq O$，我们用v×xS$v\times x^S$表示f$f$函数中的第S$S$项的系数为v$v$。

那么对于一个集合幂级数的函数f$f$，形式如下:

f=∑S⊆OfS×xS$$f=\sum _{S\subseteq O}{f}_S\times x^S$$

fS×xS$f_S\times x^S$一般简写为fSxS$f_S{x}^S$

我们以此来表示一个集合幂级数。

举个栗子，当O={1,2},F=R$O=\{1,2\},F=R$(R$R$表示实数集)，对于该函数f$f$，我们可以用f(x)=3x∅+7x{1}+6x{2}+9x{1,2}$f(x)=3x^{\varnothing }+7x^{\{1\}}+6x^{\{2\}}+9x^{\{1,2\}}$来表示一个对应系数为3,7,6,9$3,7,6,9$的集合幂级数。

我们同样定义乘法如下，对于集合幂级数h,f,g$h,f,g$,其中h=f×g$h=f\times g$，且其中的每一项满足(fIxI)×(gJxJ)=(fI×gJ)xI×J$\left(f_I{x}^I\right)\times \left(g_J{x}^J\right)=(f_I\times g_J)x^{I\times J}$，那么这个乘法就可以满足交换，结合，分配等定律了。

---

集合的并，交，对称差卷积

并

我们令三个集合幂级数f,g,h$f,g,h$，其中h$h$满足如下式子:

hS=∑I⊆O∑J⊆O[I⋃J=S]fI×gJ$$h_S=\sum _{I\subseteq O}\sum _{J\subseteq O}[I\bigcup J=S]f_I\times g_J$$

那么我们称h$h$为f,g$f,g$的集合并卷积，简记为f⨀g=h$f⨀g=h$。

交

我们令三个集合幂级数f,g,h$f,g,h$，其中h$h$满足如下式子:

hS=∑I⊆O∑J⊆O[I⋂J=S]fI×gJ$$h_S=\sum _{I\subseteq O}\sum _{J\subseteq O}[I\bigcap J=S]f_I\times g_J$$

那么我们称h$h$为f,g$f,g$的集合交卷积，简记为f⨀g=h$f⨀g=h$。

对称差

我们令三个集合幂级数f,g,h$f,g,h$，其中h$h$满足如下式子:

hS=∑I⊆O∑J⊆O[I⨁J=S]fI×gJ$$h_S=\sum _{I\subseteq O}\sum _{J\subseteq O}[I⨁J=S]f_I\times g_J$$

那么我们称h$h$为f,g$f,g$的集合对乘差卷积，简记为f⋅g=h$f\cdot g=h$或者f×g$f\times g$（能看懂就行）。

---

对于如上的三个卷积，显然都可O(|O|2)$O(|O{|}^2)$的时间复杂度计算(括号外面的O$O$为时间复杂度的符号，里面的O$O$表示全集，|O|$|O|$表示全集大小)。

但是这样肯定不能解决大多数问题，那么我们需要考虑快速算法。

---

分治是一种降低复杂度的好方法，那么这个能否分治呢？

我们将全集O$O$中的一个元素w$w$单独提出，也就是对于所有含w$w$的集合提一个w$w$出来，那么f$f$可以写成由两个集合组合出来的函数，f−$f^{-}$表示不含w$w$的部分，f+$f^{+}$表示含有w$w$的部分，那么f=f−+x{w}f+$f=f^{-}+x^{\{w\}}{f}^{+}$，由此我们可以把原式写成如下形式

f×g=(f−+x{w}f+)×(g−+x{w}g+)$$f\times g=\left(f^{-}+x^{\{w\}}{f}^{+}\right)\times \left(g^{-}+x^{\{w\}}{g}^{+}\right)$$

对于不同的⨀$⨀$，我们可以将其化简成不同的形式。

• ⨀=⋃$⨀=\bigcup$时

由于当前的运算为并，那么x{w}×x{}=x{w}$x^{\{w\}}\times x^{\{\}}=x^{\{w\}}$,x{w}×x{w}=x{w}$x^{\{w\}}\times x^{\{w\}}=x^{\{w\}}$，x{}×x{}=x{}$x^{\{\}}\times x^{\{\}}=x^{\{\}}$(有元素w$w$的与没有的并起来就有元素w$w$,都有元素w$w$并起来还是有，都没有并起来就还是没有)。

所以我们进行如下化简:

f×g=(f−+x{w}f+)×(g−+x{w}g+)$$f\times g=\left(f^{-}+x^{\{w\}}{f}^{+}\right)\times \left(g^{-}+x^{\{w\}}{g}^{+}\right)$$

=f−×g−+x{w}×(f−×g+)+x{w}×(f+×g−)+x{w}×(f+×g+)$$=f^{-}\times g^{-}+x^{\{w\}}\times \left(f^{-}\times g^{+}\right)+x^{\{w\}}\times \left(f^{+}\times g^{-}\right)+x^{\{w\}}\times \left(f^{+}\times g^{+}\right)$$

这里将乘号略写

=f−g−+x{w}(f−g+ +f+g−+f+g+)$$=f^{-}{g}^{-}+x^{\{w\}}\left(f^{-}{g}^{+}+f^{+}{g}^{-}+f^{+}{g}^{+}\right)$$

将其化简为乘积的形式

=f−g−+x{w}((f−+f+)×(g−+g+)−f−g−)$$=f^{-}{g}^{-}+x^{\{w\}}\left(\left(f^{-}+f^{+}\right)\times \left(g^{-}+g^{+}\right)-f^{-}{g}^{-}\right)$$

我们将其看作两种形式，第一种为单独的f−$f^{-}$或g−$g^{-}$，另一种为单独的(f−+f+)$(f^{-}+f^{+})$或(g−+g+)$(g^{-}+g^{+})$，那么我们通过分治的方法，先将f$f$和g$g$分别变化成f‘=(f−,(f−+f+))$f^{‘}=\left(f^{-},\left(f^{-}+f^{+}\right)\right)$和g‘=(g−,(g−+g+))$g^{‘}=\left(g^{-},\left(g^{-}+g^{+}\right)\right)$
然后对应的项乘起来，我们令h‘=f‘×g‘$h^{‘}=f^{‘}\times g^{‘}$，此时h‘=(h−,h+)=(f−g−,(f−+f+)×(g−+g+))$h^{‘}=(h^{-},h^{+})=(f^{-}{g}^{-},(f^{-}+f^{+})\times (g^{-}+g^{+}))$，但是此时的h‘$h^{‘}$并不是我们要求的h$h$，联想FFT$\mathrm{F}\mathrm{F}\mathrm{T}$的做法，既然变换过去了，肯定要找个方法变换回来。再看我们推导化简式子的最后有一个((f−+f+)×(g−+g+)−f−g−)$\left(\left(f^{-}+f^{+}\right)\times \left(g^{-}+g^{+}\right)-f^{-}{g}^{-}\right)$，所以我们将h‘$h^{‘}$变成h=(h−,h+−h−)$h=(h^{-},h^{+}-h^{-})$，就可以得到h$h$了。

复杂度分析，我们令size$size$为元素种类的大小，设总的变换的时间复杂度为T(size)$T(size)$，可得T(size)=2×T(size−1)+O(|O|)$T(size)=2\times T(size-1)+O(|O|)$，其中2×T(size−1)$2\times T(size-1)$是因为提出一个元素后，元素种类减少1，分成了本来有该元素和本来无该元素的两部分，所以乘2，再加上当前这次变换的复杂度。最后解得总复杂度T(size)=O(size×|O|)$T(size)=O(size\times |O|)$，而size$size$大小是远远小于由size$size$个元素组成的集合的全集O$O$的大小的，一般|O|=2size$|O|=2^{size}$，复杂度远远低于暴力复杂度，可以看做O(nlog2n)$O(nlo{g}_{2}n)$。

说明:例如当前size=3$size=3$，有1,2,3$1,2,3$元素，那么O={{∅},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}$O=\{\{\varnothing \},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$，所以O$O$的大小为2size=8$2^{size}=8$。

---

• ⨀=⋂$⨀=\bigcap$时

同样对于交，我们化简原式，过程略，得到如下式子:

乘号略写公式太难打了QAQ。

f⋅g=f−g−+f+g−+f−g++x{w}(g+f+)$$f\cdot g=f^{-}{g}^{-}+f^{+}{g}^{-}+f^{-}{g}^{+}+x^{\{w\}}(g^{+}{f}^{+})$$

说明:因为交是必须两个都有w$w$元素，最后才会有，否则就没有w$w$元素。

写成乘积形式

=((f−+f+)⋅(g−+g+)−f+g+)+x{w}(g+f+)$$=\left((f^{-}+f^{+})\cdot (g^{-}+g^{+})-f^{+}{g}^{+}\right)+x^{\{w\}}(g^{+}{f}^{+})$$

同样的，提出类似的部分后，我们可以对f,g$f,g$先自己变换，然后相乘(对应项)，然后再变换一次变回来就可以求出h$h$。

其中f‘=((f−+f+),f+),g‘=((g−+g+),g+),h=(h−−h+),h+$f^{‘}=((f^{-}+f^{+}),f^{+}),g^{‘}=((g^{-}+g^{+}),g^{+}),h=(h^{-}-h^{+}),h^{+}$

复制度同上。

---

• ⨀=⨁$⨀=⨁$时

对于对称差，都是大同小异。

化简后得到

f⋅g=(f−g−+f+g+)⋅x{w}(f−g++f+g−)$$f\cdot g=(f^{-}{g}^{-}+f^{+}{g}^{+})\cdot x^{\{w\}}(f^{-}{g}^{+}+f^{+}{g}^{-})$$

说明:因为对称差计算有点奇怪好吧其实也不奇怪,两者都有或者都没有该元素，计算出来就没有。只要其中一个有另一个没有，计算出来就有。

所以变换为:

f‘=((f−+f+),(f−−f+))$f^{‘}=((f^{-}+f^{+}),(f^{-}-f^{+}))$
g‘$g^{‘}$同理。

h=((h−+h+)2,(h−−h+)2)$h=(\frac{(h^{-}+h^{+})}{2},\frac{(h^{-}-h^{+})}{2})$

自己手推一下应该可以得到。

• 对称差的另外一种推导方法

我们这么半天，集合幂级数的性质也没太明显用，下面就将对称差的另外一种推导方法。

首先引入如下式子：

对于一个集合S$S$有：

12size∑T⊆O(−1)|S⋂T|=[S=∅]$$\frac{1}{2^{size}}\sum _{T\subseteq O}(-1{)}^{|S\bigcap T|}=[S=\varnothing ]$$

对于证明我们较容易发现，当S=∅$S=\varnothing$时|S⋂T|$|S\bigcap T|$恒为0$0$，那么(−1)|S⋂T|$(-1{)}^{|S\bigcap T|}$也就恒为1，又因为|O|=2size$|O|=2^{size}$，所以最后除以了一个2size$2^{size}$，式子的值就为1。对于S$S$不为空集，令一个元素v∈S$v\in S$，由于(−1)|S⋂(T⨁{v})|$(-1{)}^{|S\bigcap (T⨁\{v\})|}$，根据对称差的分配律S⋂(T⨁{v})=(S⨁{v})⋂(T⨁{v})=(S⋂T)⨁{v}$S\bigcap (T⨁\{v\})=(S⨁\{v\})\bigcap (T⨁\{v\})=(S\bigcap T)⨁\{v\}$，原式等于(−1)|(S⋂T)⨁{v}|$(-1{)}^{|(S\bigcap T)⨁\{v\}|}$，又因为S⋂T$S\bigcap T$中没有{v}$\{v\}$交集大小增加1，有{v}$\{v\}$交集大小减少1，所以怎么都要变化1，所以(−1)|(S⋂T)⨁{v}|=−(−1)|S⋂T|$(-1{)}^{|(S\bigcap T)⨁\{v\}|}=-(-1{)}^{|S\bigcap T|}$，那么可以得知(−1)|S⋂T|+(−1)|(S⋂T)⨁{v}|=0$(-1{)}^{|S\bigcap T|}+(-1{)}^{|(S\bigcap T)⨁\{v\}|}=0$，由于T⨁{v}⨁{v}=T$T⨁\{v\}⨁\{v\}=T$，所以T$T$与T⨁{v}$T⨁\{v\}$一一对应，所以最后原式的值肯定为0。

我们接下来看：

h=f⋅g$$h=f\cdot g$$

对于一个集合S$S$，可知

hS=∑I⊆O∑J⊆O[I⨁J=S]fI⋅gJ$$h_S=\sum _{I\subseteq O}\sum _{J\subseteq O}[I⨁J=S]f_I\cdot g_J$$

=∑I⊆O∑J⊆O[I⨁J⨁S=∅]fI⋅gJ$$=\sum _{I\subseteq O}\sum _{J\subseteq O}[I⨁J⨁S=\varnothing ]f_I\cdot g_J$$

=∑I⊆O∑J⊆O12size∑T⊆O(−1)|(I⨁J⨁S)⋂T| fI⋅gJ$$=\sum _{I\subseteq O}\sum _{J\subseteq O}\frac{1}{2^{size}}\sum _{T\subseteq O}(-1{)}^{|(I⨁J⨁S)\bigcap T|}{f}_I\cdot g_J$$

=∑I⊆O∑J⊆O12size∑T⊆O(−1)|T⋂I|(−1)|T⋂J|(−1)|T⋂S| fI⋅gJ$$=\sum _{I\subseteq O}\sum _{J\subseteq O}\frac{1}{2^{size}}\sum _{T\subseteq O}(-1{)}^{|T\bigcap I|}(-1{)}^{|T\bigcap J|}(-1{)}^{|T\bigcap S|}{f}_I\cdot g_J$$

说明:这里能这样变换是因为(−1)×(−1)=1$(-1)\times (-1)=1$对答案无影响，会消掉，所以如果I⨁J⨁S$I⨁J⨁S$有或者没有某个元素，和T$T$交后，会被如上方法抵消影响。

举个栗子：I,J,S$I,J,S$的某个元素{v}$\{v\}$的有无情况如下(因为都与T$T$相交，所以可以不管T$T$的影响):
{1,0,0}{0,1,0}{0,0,1}{1,1,1}$\{1,0,0\}\{0,1,0\}\{0,0,1\}\{1,1,1\}$，此时 I⨁J⨁S$I⨁J⨁S$会有该元素，但是三种情况分别为(−1)1,(−1)3$(-1{)}^1,(-1{)}^3$都为−1$-1$不变，同样I⨁J⨁S$I⨁J⨁S$没有该元素的都为1$1$不变，所以可以拆开，其实因为⨁$⨁$出来有该元素必须有奇数个1，无该元素必须有偶数个1，所以(−1)$(-1)$的奇数次方为-1，偶数次方为0，而奇数⨁$⨁$出来有该元素，就是(−1)1$(-1{)}^1$还是−1$-1$，偶数没有，就是(−1)0$(-1{)}^0$，所以为1。

=12size∑T⊆O(−1)|T⋂S|(∑I⊆O(−1)|T⋂I|fI)(∑J⊆O(−1)|T⋂J|gJ)$$=\frac{1}{2^{size}}\sum _{T\subseteq O}(-1{)}^{|T\bigcap S|}\left(\sum _{I\subseteq O}(-1{)}^{|T\bigcap I|}{f}_I\right)\left(\sum _{J\subseteq O}(-1{)}^{|T\bigcap J|}{g}_J\right)$$

这里前半部分12size∑T⊆O(−1)|T⋂S|$\frac{1}{2^{size}}\sum _{T\subseteq O}(-1{)}^{|T\bigcap S|}$只有当S=∅$S=\varnothing$时后半部分才为1，所以这个式子的值为1，然后对于单个集合f$f$的变换，我们可以将集合g$g$看作一个常量，也就是式子最后半部分关于g$g$的那个括号里的值可以看作1，所以这种形式可以启发我们定义以下变换。

这样我们就可以定义一种变换，对于一个集合幂级数f$f$，我们定义它的沃尔什变换为集合幂级数f∧$f^{\wedge }$,其中:

f∧S=∑T⊆OfT(−1)|S⋂T|$$f_S^{\wedge }=\sum _{T\subseteq O}{f}_T(-1{)}^{|S\bigcap T|}$$

其逆变换同样由上面推导式得到:

fS=12size∑T⊆Of∧T(−1)|S⋂T|$$f_S=\frac{1}{2^{size}}\sum _{T\subseteq O}{f}_T^{\wedge }(-1{)}^{|S\bigcap T|}$$

再从集合对称差卷积得到:

h∧S=f∧Sg∧S$$h_S^{\wedge }=f_S^{\wedge }{g}_S^{\wedge }$$

于是我们先可以对f,g$f,g$做沃尔什变换，再相乘得到h∧$h^{\wedge }$然后对其做沃尔什逆变换得到答案h$h$

这里可以用递推的方法，我们设f∧(i)S$f_S^{\wedge (i)}$为只考虑那些与S$S$的对称差是{1,…,i}$\{1,\dots ,i\}$的子集的沃尔什变换的第S$S$项(也就是T⨁S⊆{1,…,i}$T⨁S\subseteq \{1,\dots ,i\}$的集合T$T$的fT(−1)|S⋂T|$f_T(-1{)}^{|S\bigcap T|}$之和)，这里容易得到对于不包含i$i$的S$S$有

f∧(i)S=f∧(i−1)S−f∧(i−1)S⋃{i}$$f_S^{\wedge (i)}=f_S^{\wedge (i-1)}-f_{S\bigcup \{i\}}^{\wedge (i-1)}$$

f∧(i)S⋃{i}=f∧(i−1)S+f∧(i)S⋃{i}$$f_{S\bigcup \{i\}}^{\wedge (i)}=f_S^{\wedge (i-1)}+f_{S\bigcup \{i\}}^{\wedge (i)}$$

说明:对于第一个式子,不含有{i}$\{i\}$元素的f∧(i)S$f_S^{\wedge (i)}$根据定义式=∑T⊆OfT(−1)|S⋂T|$=\sum _{T\subseteq O}{f}_T(-1{)}^{|S\bigcap T|}$，将其拆分为两部分=∑T⊆OfT(−1)|S⋂T|[{i}∉T]+∑T⊆OfT(−1)|S⋂T|[{i}∈T]$=\sum _{T\subseteq O}{f}_T(-1{)}^{|S\bigcap T|}[\{i\}\notin T]+\sum _{T\subseteq O}{f}_T(-1{)}^{|S\bigcap T|}[\{i\}\in T]$,对于前半部分因为已经是S$S$不含有i$i$了，但是对于后者，我们要用S⋃{i}$S\bigcup \{i\}$来表示，所以当S$S$换成S⋃{i}$S\bigcup \{i\}$时，|S⋂T|$|S\bigcap T|$变成|(S⋃{i})⋂T|$|(S\bigcup \{i\})\bigcap T|$，它的集合大小会增加1，因为开始S$S$中没有{i}$\{i\}$，交出来也没有，后面|S⋃{i}|$|S\bigcup \{i\}|$中有了，所以交出来就比原来多了一个{i}$\{i\}$(这里的T$T$中是有{i}$\{i\}$的),所以∑T⊆OfT(−1)|S⋂T|[{i}∈T]=−∑T⊆OfT(−1)|(S⋃{i})⋂T|     [{i}∈T]$\sum _{T\subseteq O}{f}_T(-1{)}^{|S\bigcap T|}[\{i\}\in T]=-\sum _{T\subseteq O}{f}_T(-1{)}^{|(S\bigcup \{i\})\bigcap T|}[\{i\}\in T]$，所以可以得到一式。
对于二式，也是同样的道理，开始变成了含有{i}$\{i\}$的集合S⋃{i}$S\bigcup \{i\}$,同样用定义式将其拆成两部分∑T⊆OfT(−1)|(S⋃{i})⋂T|     [{i}∉T]+∑T⊆OfT(−1)|(S⋃{i})⋂T|     [{i}∈T]$\sum _{T\subseteq O}{f}_T(-1{)}^{|(S\bigcup \{i\})\bigcap T|}[\{i\}\notin T]+\sum _{T\subseteq O}{f}_T(-1{)}^{|(S\bigcup \{i\})\bigcap T|}[\{i\}\in T]$，然后后半部分已经为S⋃{i}$S\bigcup \{i\}$所以要将前半部分变成没有{i}$\{i\}$的S$S$,同样来看，|(S⋃{i})⋂T|$|(S\bigcup \{i\})\bigcap T|$和|S⋂T|$|S\bigcap T|$没有变化，因为这里的T$T$是不包含{i}$\{i\}$元素的，所以可以得到二式。

但是对于最底层的f∧(0)S$f_S^{\wedge (0)}$，根据定义来看，我们最底层的T$T$只能等于S$S$，这样S⨁T=∅$S⨁T=\varnothing$，所以f∧(0)S$f_S^{\wedge (0)}$，当S$S$大小为奇数时它等于−fS$-f_S$，为偶数时他就等于fS$f_S$，这样十分不好处理，所以我们统一规定，f∧(0)S=fS$f_S^{\wedge (0)}=f_S$，那么对于上面求出的式子也要进行改动。

我们这里假设(−1)|S⋂T|=1$(-1{)}^{|S\bigcap T|}=1$,那么(−1)|(S⋃{i})⋂T|=−1$(-1{)}^{|(S\bigcup \{i\})\bigcap T|}=-1$,(其实反过来也可以，虽然式子符号（正负）会变，最终的答案不会改变),因为后者会比前者多一个元素{i}$\{i\}$，所以f∧(i)S⋃{i}$f_{S\bigcup \{i\}}^{\wedge (i)}$本来要乘以−1$-1$，又因为我们上面的重定义，所以不能乘以−1$-1$，所以对于后者要取相反数，这里我们便得到了最终的集合对称差卷积的沃尔什变换的式子:

f∧(i)S=f∧(i−1)S+f∧(i−1)S⋃{i}$$f_S^{\wedge (i)}=f_S^{\wedge (i-1)}+f_{S\bigcup \{i\}}^{\wedge (i-1)}$$

f∧(i)S⋃{i}=f∧(i−1)S−f∧(i)S⋃{i}$$f_{S\bigcup \{i\}}^{\wedge (i)}=f_S^{\wedge (i-1)}-f_{S\bigcup \{i\}}^{\wedge (i)}$$

其实也就和之前的证明方法的结果相同了，f∧=(f−+f+,f−−f+)$f^{\wedge }=(f^{-}+f^{+},f^{-}-f^{+})$。

逆变换也就是原来的变换乘以了12size$\frac{1}{2^{size}}$，所以我们发现这里可以不用像原来的逆变换每次除以2，可以做顺变换，最后答案除以2size$2^{size}$即可。

注：对于其它两个集合运算也有类似的证明，但是过于繁琐，而且实际应用中集合对称差用到此证明公式的最多，所以其余两个就不讲此类证法，有兴趣的读者可自行查阅资料。

---

到这里，沃尔什变换就大概完整了。

三种卷积的变换与逆变换

集合并⋃$\bigcup$

• 沃尔什变换 f∧=(f−,f−+f+)$f^{\wedge }=(f^{-},f^{-}+f^{+})$

• 沃尔什逆变换 f=(f∧−,f∧+−f∧−)$f=(f^{\wedge -},f^{\wedge +}-f^{\wedge -})$

集合交⋂$\bigcap$

• 沃尔什变换 f∧=(f−+f+,f+)$f^{\wedge }=(f^{-}+f^{+},f^{+})$

• 沃尔什逆变换 f=(f∧−−f∧+,f∧+)$f=(f^{\wedge -}-f^{\wedge +},f^{\wedge +})$

集合对称差⨁$⨁$

• 沃尔什变换 f∧=(f−+f+,f−−f+)$f^{\wedge }=(f^{-}+f^{+},f^{-}-f^{+})$

• 沃尔什逆变换 f=(f∧−+f∧+2,f∧−−f∧+2)$f=(\frac{f^{\wedge -}+f^{\wedge +}}{2},\frac{f^{\wedge -}-f^{\wedge +}}{2})$

  注意：在取模运算时，除2要变成乘以2对应的逆元。

---

那么对于全集的每个元素，我们可以用0或者1来表示它是否在某个集合里，就可以用一个二进制数来表示集合，这在运算上就十分方便了，原因如下:

• 对于集合并，它就相当于位运算中的|(or)$|(or)$，1011⋃0110=1111$1011\bigcup 0110=1111$ , 1011|0110=1111$1011|0110=1111$。

• 对于集合交，它就相当于位运算中的&(and)，1011⋂0110=0010$1011\bigcap 0110=0010$ , 1011&0110=0010。

• 对于集合对称差，你应该想到了，没错，它就是∧(xor)$\wedge (xor)$ ，1011⨁0110=1101$1011⨁0110=1101$ ，1011∧0110=1101$1011\wedge 0110=1101$

---

那么由于位运算每一位之间互不影响，所以我们可以把它按照当前位为0或1分治，也就是表示当前元素有无分治。

但是递归虽然可以，有时常数以及实际效率并不是很优秀，所以我们考虑不用递归的形式。

我们发现它的全集O$O$，可以用二进制数全部表示出来，转换为十进制来看就是{0,1,2,…,2size−1}$\{0,1,2,\dots ,2^{size}-1\}$，其中0$0$表示∅$\varnothing$。

那么我们来看二进制的形式：

{0,1,2,3,4,5,6,7}$\{0,1,2,3,4,5,6,7\}$就等于

{000,001,010,011,100,101,110,111}$\{000,001,010,011,100,101,110,111\}$

我们发现对于第i$i$位(从右往左数)，它为0$0$相隔2i−1$2^{i-1}$个数，为1$1$也是，如1:{0,1,0,1,0,1,0,1}$1:\{0,1,0,1,0,1,0,1\}$,2:{0,0,1,1,0,0,1,1}$2:\{0,0,1,1,0,0,1,1\}$,3:{0,0,0,0,1,1,1,1}$3:\{0,0,0,0,1,1,1,1\}$，以此类推，所以我们可以用循环来代替递归。

第一层循环，枚举当前为第i$i$位

for(int bit=1;bit<(1<<size);bit<<=1)

第二次枚举当前连续的一段0和1

int inc=bit<<1;
for(int i=0;i<(1<<size);i+=inc)

依次枚举这一段对应的0和1,

for(int j=0;j<bit;j++)

那么我们用x$x$表示0这一位，y$y$表示1这一位，那么就有

x=a[i+j],y=a[i+j+bit];
//eg.当前这一位是{0,0,1,1,0,0,1,1}
//               |   |
//               i   i+bit
// j {0~1}

所以对于三种变化我们计算如下

运算方式	or并	and交	xor对称差
沃尔什变换	a[i+j+bit]=x+y	a[i+j]=x+y	a[i+j]=x+y,a[i+j+bit]=x-y
沃尔什逆变换	a[i+j+bit]=y-x	a[i+j]=x-y	a[i+j]=(x+y)/2,a[i+j+bit]=(x-y)/2

那么代码就很容易写了。
模板题目

Luogu P4717
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=1<<19;
const ll mod=998244353ll;
int n;
ll A[M],B[M];
ll a[M],b[M];
ll c[3][M],inv;
ll pow(ll a){
    ll b=mod-2,ans=1;
    for(;b;b>>=1,a=(a*a)%mod){
        if(b&1) ans=(ans*a)%mod;
    }
    return ans;
}
void WT(ll *w,int n,int f,int type){
    ll x,y;
    //type:0 or,1 and,2 xor
    //f=1 沃尔什变换 f=-1 沃尔什逆变换
    for(int d=1;d<n;d<<=1){
        for(int ad=d<<1,i=0;i<n;i+=ad){
            for(int j=0;j<d;j++){
                x=w[i+j],y=w[i+j+d];
                if(f==1){
                    switch(type){
                        case 0:{
                            w[i+j+d]=(x+y)%mod;
                            break;
                        }
                        case 1:{
                            w[i+j]=(x+y)%mod;
                            break;
                        }
                        case 2:{
                            w[i+j]=(x+y)%mod;
                            w[i+j+d]=(x-y+mod)%mod;
                            break;
                        }
                    }
                }else{
                    switch(type){
                        case 0:{
                            w[i+j+d]=(y-x+mod)%mod;
                            break;
                        }
                        case 1:{
                            w[i+j]=(x-y+mod)%mod;
                            break;
                        }
                        case 2:{
                            w[i+j]=(x+y)*inv%mod;
                            w[i+j+d]=(((x-y)*inv%mod)+mod)%mod;
                            break;
                        }
                    }
                }
            }
        }
    }
}
void FWT(ll *a,ll *b,int n){
    for(int f=0;f<3;f++){
        memset(A,0,sizeof(A));memset(B,0,sizeof(B));
        for(int i=0;i<n;i++) A[i]=a[i],B[i]=b[i];
        WT(A,n,1,f);WT(B,n,1,f);
        for(int i=0;i<n;i++) A[i]=(A[i]*B[i])%mod;
        WT(A,n,-1,f);
        for(int i=0;i<n;i++) c[f][i]=(A[i]%mod+mod)%mod;
    }
}

int main(){
    inv=pow(2);
    scanf("%d",&n);n=(1<<n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    for(int i=0;i<n;i++) scanf("%lld",&b[i]);
    FWT(a,b,n);
    for(int i=0;i<3;i++){
        for(int j=0;j<n;j++) printf("%lld ",c[i][j]);puts("");
    }
    return 0;
}

hdxrie的更简洁的模板IN THERE
其中有一些简单的特判，避免了我的switch语句的麻烦。(感谢hdxrie提供)

而暴力计算其实十分简单，为了方便理解，这里放一份暴力代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=1<<19;
const ll mod=998244353ll;
int n;
ll a[M],b[M];
ll cxor[M],cor[M],cand[M];
int main(){
    scanf("%d",&n);
    if(n>13) return 0;
    n=(1<<n);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    for(int i=0;i<n;i++)scanf("%lld",&b[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ll now=(a[i]*b[j])%mod;
            (cor[i|j]+=now)%=mod;
            (cxor[i^j]+=now)%=mod;
            (cand[i&j]+=now)%=mod;
        }
    }
    for(int i=0;i<n;i++) printf("%lld ",cor[i]);puts("");
    for(int i=0;i<n;i++) printf("%lld ",cand[i]);puts("");
    for(int i=0;i<n;i++) printf("%lld ",cxor[i]);puts("");
    return 0;
}

End

这里就结束了，如果有不清楚或者错误的地方，欢迎向我提出，我会尽量及时回答与修改(我也是个初学者)。

参考

• 百度一下

• 大佬讲解

• 很好的讲解

• 其它的1

• 其它的2

• 其它的3

• 国家集训队2015文章

具体应用与题目

参考这篇文章

• 大佬讲解

Thanks♪(･ω･)ﾉ for reading！