集合卷积：
\[c_{i}= \sum_{j \otimes k = i}a_jb_k
\]
其中 \(\otimes\) 可以取：或 \(\cup\)，与 \(\cap\)，异或 \(\oplus\)，同或（?）。
\(\otimes=\cup\)
FWT 的想法是，效仿 FFT 通过转化为点值相乘快速进行卷积。那么这里就需要构造一种方法：
对于 FFT 来说，下标是相加：
\[c_{i}= \sum_{j + k = i}a_jb_k
\]
利用了幂的性质 \(x^{i+j}=x^ix^j\) 转化为函数相乘，然后通过一些小转化求这个卷积式。
对于 FWT 来说，下标是相或：
\[c_{i}= \sum_{j \cup k = i}a_jb_k
\]
那我能不能构造一个运算法则，使得 \(x^ix^j=x^{i \cup j}\)？
注意到（?）：
\[\begin{aligned} \sum _{p\cup i=i} c_p&=\sum_{p \cup i=i}\sum_{j \cup k = p}a_{j}b_k\\ &=\sum_{j \cup k \cup i = i}a_{j}b_k\\ &=\sum_{j\cup i=i}a_j\sum_{k \cup i=i}b_k \end{aligned} \]
于是令：
\[FWT(a)_i=\sum_{j \cup i=i} a_i=\sum_{j \subseteq i}a_i
\]
就有：\(FWT(c)_i=FWT(a)_i\times FWT(b)_i\)。
接下来是求快速求 \(FWT(a)\) 和逆变换 \(IFWT(a)\) 的娱乐时间：
应用铁锹的方法，写一个 \(2^2\) 的例子：
\[\begin{array}{ll}
i&00&01&10&11\\
FWT_i&00&00+01&00+10&00+01+10+11\\
\end{array}
\]
先按最高位砍成两半：\(0\_,1\_\)，发现左边的属于是一个子问题，分治下去就行；
右边的难道就不是子问题吗？去掉左边的影响，右边分别为 \(10\) 和 \(10+11\)，那么去除最高位仍然是一个子问题，分治即可。
令左半边为 \(a_0\), 右半边为 \(a_1\)，那么：
\(FWT(a)=\mathrm{merge}(FWT(a_0),FWT(a_1)+FWT(a_0))\)，这是容易证明的。（\(+\) 表示逐个元素地加）
容易写出简易的迭代版本。\(IFWT\) 同理，将 \(+ \to -\) 即可。