前置知识
- 多项式基础
- 快速傅里叶变换/数论变换（FFT/FNTT）
- 位运算（集合运算）
引入·位运算卷积
典型的 FFT, NTT 被用于解决 加法卷积 问题。具体地，它可以解决的基本问题是：给定 \(\{f(i)\}, \{g(i)\}\) ，求：
\[\{h(i) = \sum\limits_{k+t=i}f(k)\cdot g(t)\} \]而 FMT, FWT 对应地，用来解决一类被称为 位运算卷积 的问题。这类问题的基本形式为：给定 \(\{f(i)\}, \{g(i)\}\) ，求：
\[\{h(i) = \sum\limits_{k\star t=i}f(k)\cdot g(t)\}\\ (其中\star\in\{|, \&, \oplus, \odot\}) \]其中，用于 \(|, \&\) 的是 快速莫比乌斯变换 ，用于 \(\oplus, \odot\) 的是 快速沃尔什变换 ，它们的原理有一定差异。然而，无论是 FFT 还是其它多项式变换，核心都是将复杂的 卷积 转化成简单的 点乘 运算，从而加快计算。
注意到“或”和“与”、“异或”和“同或”同构，所以下文主要分析“或卷积”和“异或卷积”，同时也给出后两者的式子和实现。
二进制位运算和集合的交、并、对称差运算有着等价关系，所以 FMT, FWT 也可以被用于集合的处理。后文也将集合的符号如 \(|A|\) 、\(\subseteq\) 等应用于二进制整数。
快速莫比乌斯变换
正变换
快速莫比乌斯变换的核心是 高维前缀和和子集反演 。首先推一个或运算卷积的基本式子：
\[设F(x) = \sum\limits_{i\subseteq x}f(i),G(x) = \sum\limits_{i\subseteq x}g(i), H(x) = \sum\limits_{i\subseteq x}h(i);\\ \begin{align*} 则F(x)\cdot G(x) &= \left(\sum\limits_{i\subseteq x}{f(i)}\right)\cdot\left(\sum\limits_{i\subseteq x}{g(i)}\right)\\ &= \sum\limits_{i\subseteq x}{\sum\limits_{j\subseteq x}{f(i)\cdot g(j)}}\\ &= \sum\limits_{y\subseteq x}{\sum\limits_{i|j=y}{f(i)\cdot g(j)}}\\ &= \sum\limits_{y\subseteq x}{g(y)}\\ &= H(x) \end{align*} \]类比 FFT 的知识，可以看出，这个式子就给出了从 卷积 到 点乘 的变换。然而，暴力计算上式是 \(\Theta(n^2)\) 的，当然，通过 \(\Theta(3^{|S|})\) 枚举子集的技术，可以把复杂度优化到\(\Theta(3^{\log_2n}) = \Theta(n^{1.585})\)，但这显然不够。运用一些高维前缀和技巧，这一复杂度可以被优化到\(\Theta(n\log n)\)。这就是 FMT。
具体地，在计算数组 \(\{F(x)\}\) 时，FMT 依次考虑 \(x\) 的二进制位。设 \(B_i(x)\) 表示 \(x\) 在二进制下的第 \(i\) 位；再定义 \(F_i(x)\) ：
\[F_i(x) = \sum\limits_{y}{[\forall j \le i, B_j(y) \le B_j(x);~\forall j > i, B_j(y) = B_j(x)]f(y)} \]也就是说，\(F_i(x)\) 是 \(f(x)\) 二进制 \(i\) 位以前的前缀和，而 \(i+1\) 位开始的位则原封不动，不进行前缀和。因此有 \(F_{|n|}(x) = F(x)\) 即为待求多项式（其中 \(|n|\) 表示 \(n\) 的二进制位数——也就是最大的 \(x\) 的二进制位数），另外设 \(F_{-1}(x) = f(x)\) 表示什么也没有组合。
接下来，考虑当前正在计算 \(F_k(x), k\ge 0\) 。那么有：
\[F_k(x) = \begin{cases} F_{k-1}(x) + F_{k-1}(x-2^k), &B_k(x) = 1\\ F_{k-1}(x), &B_k(x) = 0 \end{cases} \]这是因为，对于所有元素，它 \(k-1\) 之前的前缀和已经保存在 \(F_{k-1}\) ，现在直接组合第 \(k\) 位，得到的就是 \(k\) 位之前的前缀和。
逆变换
根据 FMT 基本式，逆变换的实质就是：
\[已知F(x) = \sum\limits_{i\subseteq x}f(i)，求f(x) \]这就是子集反演。直接带入：
\[f(x) = \sum\limits_{i\subseteq x}(-1)^{|x|-|i|}F(i) \]这个形式比正变换多了一个容斥系数。考察一下前面的推导，看看那些部分需要改。因为 FMT 计算高维前缀和的过程就是在逐位累计，而 \((-1)^{|x|-|i|}\) 的值变化当且仅当|x|增加一位（ \(i\) 的部分是不变的，始终是 \((-1)^{-|i|}\) 同 \(F(i)\) 相对应），也就是当前集合的二进制位多了一位，所以只需要在这些时候考虑即可。
具体地，计算 \(f_k(x)\) 时，当且仅当将 \(f_{k-1}(x-2^k)\) 累计到 \(f_{k}(x)\)中时，集合 \(x\) 变大 1。因此将转移式修改为：
\[f_k(x) = \begin{cases} f_{k-1}(x) - f_{k-1}(x-2^k), &B_k(x) = 1\\ f_{k-1}(x), &B_k(x) = 0 \end{cases} \]而对于初值\(f_{-1}(x)\) ，因为没有做前缀和，所以 \(|x| - |i| = 0\) ，则 \(f_{-1}(x) = F(x)\) 。
与运算卷积
仅给出式子：
\[\begin{align} &F(x) = \sum\limits_{x\subseteq i}f(i)\\ &F_i(x) = \sum\limits_{y}{[\forall j \le i, B_j(y) \ge B_j(x);~\forall j > i, B_j(y) = B_j(x)]f(y)}\\ &F_k(x) = \begin{cases} F_{k-1}(x) + F_{k-1}(x+2^k), &B_k(x) = 0\\ F_{k-1}(x), &B_k(x) = 1 \end{cases}\\ &f_k(x) = \begin{cases} f_{k-1}(x) - f_{k-1}(x+2^k), &B_k(x) = 0\\ f_{k-1}(x), &B_k(x) = 1 \end{cases} \end{align} \]实现
// 不想写了