FMT 和 FWT 入门
FLY_lai
·
·
算法·理论
【预备知识】
子集反演公式：
f(S)=\sum_{T\subseteq S}g(T)\iff g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)
f(S)=\sum_{S\subseteq T}g(T)\iff g(S)=\sum_{S\subseteq T}(-1)^{|S|-|T|}f(T)
如果用 g 直接暴力算 f，复杂度是 O(3^n) 的；使用 SOSDP 则可以把复杂度优化至 O(n\cdot 2^n)，具体不再赘述。
（f 子集反演算 g 也可以 SOSDP，同样 O(n\cdot 2^n) 求）
【FMT】
FMT，快速莫比乌斯变换。它解决这么一个问题：
给定两个序列 a_0\sim a_{2^n-1} 和 b_0\sim b_{2^n-1}，求序列 c_0\sim c_{2^n-1}，满足：将下标 I 看作 n 大小的子集，c_I=\sum_{J\cup K=I}a_J\cdot b_K。
这种问题叫或卷积。
记 N=2^n，首先容易发现有一个 O(N^2) 的解法，即枚举 J,K 累加答案。
FMT 可以用来解决这类问题，复杂度为 O(N\log N)=O(2^n\cdot n)，和 SOSDP 一样。
下面介绍一下 FMT。
在开始之前，我们先回顾一下 FFT 是怎么做普通卷积的。
-
对 a,b 分别做 DFT。
-
求出 c 的 DFT。
-
做 iDFT 求出 c。
这个做法的关键在于：存在一个变换 DFT，使得 DFT 和 iDFT 做起来都很快，而且 \mathrm{DFT}(a*b)=\mathrm{DFT}(a)\cdot \mathrm{DFT}(b)。
然后回到原问题。我们记 a\oplus b 为 a,b 的或卷积。
为了解决问题，我们希望找到变换 t 满足：t 和 it 都很快，且 \mathrm{t}(a\oplus b)=\mathrm{t}(a)\cdot \mathrm{t}(b)。
一个很牛的事实是，这种变换确实存在，它们叫做 DMT 和 iDMT。即莫比乌斯变换和逆莫比乌斯变换。
介绍一下，\mathrm{DMT}(a)=(\overline{a_0},\dots,\overline{a_N})，其中 \overline{a_I}=\sum_{J\subseteq I}a_J。即把 a 变换为它的前缀和。显然做这个变换和逆变换可用 SOSDP 在 O(n\cdot 2^n) 做，问题只剩下一个性质。
引理：c=a\oplus b，则 \overline{c}=\overline{a}\cdot\overline{b}。
证明：
\begin{aligned}
\overline{c_X}&=\sum_{I\subseteq X}c_I\\
&=\sum_{I\subseteq X}\sum_{J\cup K=I}a_J\cdot b_K\\
&=\sum_{J\subseteq X}\sum_{K\subseteq X}a_J\cdot b_K\\
&=(\sum_{J\subseteq X}a_J)\cdot (\sum_{K\subseteq X}b_K)\\
&=\overline{a_X}\cdot \overline{b_X}
\end{aligned}
因此可以 O(n\cdot 2^n) 求 a,b 的高维前缀和，乘起来之后再用子集反演 O(n\cdot 2^n) 求出 c。
另外，FMT 还可以做与卷积：把 \overline{a_I}=\sum_{J\subseteq I}a_J 换做 \overline{a_I}=\sum_{I\subseteq J}a_J 即可。证明过程也类似，方向换一下即可。
【FWT】
FWT，快速沃尔什变换，用于解决异或卷积问题。问题定义类似。
同样地，我们要找一个变换 t，同样满足上面的性质。
而一样很牛的事实是，这样的变换也存在，叫做 DWT 和 iDWT。
看起来相当奇怪。
先说明 DWT 和 iDWT 都可以 $O(n\cdot 2^n)$ 计算。
**引理**：$\mathrm{iDWT}(a)=\mathrm{DWT}(a)/2^n$。
**引理证明**：
转证 $\mathrm{DWT}(\mathrm{DWT}(a))=a\cdot 2^n$，这和引理是等价的。
为什么呢？
令 $b=\mathrm{DWT}(a)$，由原本引理有 $\mathrm{DWT}(b)=a\cdot 2^n\iff\mathrm{DWT}(b)/2^n=a\iff \mathrm{DWT}(b/2^n)=a\iff b/2^n=\mathrm{iDWT}(a)$，能这么做的原因是 DWT 其实是**线性变换**，所以 $\mathrm{DWT}(x)/C=\mathrm{DWT}(x/C)$。
接下来证明转化命题。不妨设 $b=\mathrm{DWT}(a),c=\mathrm{DWT}(b)$，求证 $c_I=a_I\cdot 2^n$。
$$
\begin{aligned}
c_I&=\sum_{J}(-1)^{|I\cap J|}b_J=\sum_{J}(-1)^{|I\cap J|}\sum_{K}(-1)^{|J\cap K|}a_K\\
&=\sum_{K}a_K\sum_{J}(-1)^{|I\cap J|}(-1)^{|J\cap K|}\\
&=\sum_{K}a_K\sum_{J}(-1)^{|I\cap J|\oplus|J\cap K|}\\
&=\sum_{K}a_K\sum_{J}(-1)^{|(I\oplus K)\cap J|}\\
\end{aligned}
$$
观察上式，$(I\oplus K)\cap J$ 有什么规律？当 $I\oplus K=\empty$ 时，$J$ 无论怎么取，系数都是 $1$，因此 $\sum_J(-1)^{\cdots}=2^n$；而 $I\oplus K\neq \empty$ 时，系数会正负抵消，总共的贡献为 $0$。
因此，$\sum_{J}(-1)^{|(I\oplus K)\cap J|}=2^n$，得证。
-------------
**算法**：只考虑怎么 DWT。
设 $f$ 为 $a$ 的前 $2^{n-1}$ 项的 $2^{n-2}\sim 2^0$ 位的结果，$g$ 为后 $2^{n-1}$ 项的 $2^{n-2}\sim 2^0$ 位的结果。**注意是只考虑更低位。**
有结论：$\mathrm{DWT}(a)=(\mathrm{DWT}(f)+\mathrm{DWT}(g),\mathrm{DWT}(f)-\mathrm{DWT}(g))$，即前一半项是求和，后一半项是做差。
如果有这个结论，很显然就可以分治 $O(N\log N)=O(n\cdot 2^n)$ 来做。其实这和 FFT 非常相似，区别只在于 DFT 是按照奇偶分治下去，DWT 直接按下标分治。
问题只在于结论证明。
------------------
**求证**：$\forall 0\le I< 2^{n-1}$，$\hat{a_I}=\hat{f_I}+\hat{g_I}$，$\hat{a}_{I+2^{n-1}}=\hat{f}_I-\hat{g}_I$。
**证明**：
$$
\begin{aligned}
\hat{a}_I(I<2^{n-1})&=\sum_{0\le J<2^n}(-1)^{|I\cap J|}a_J\\
&=\sum_{0\le J<2^{n-1}}(-1)^{|I\cap J|}a_J
+\sum_{2^{n-1}\le J<2^n}(-1)^{|I\cap J|}a_J\\
&=\hat{f}_I+\sum_{2^{n-1}\le J<2^n}(-1)^{|I\cap J|}a_J\\
&=\hat{f}_I+\sum_{0\le J'<2^{n-1}}(-1)^{|I\cap (J'+2^{n-1})|}a_{J'+2^{n-1}}\\
&=\hat{f}_I+\sum_{0\le J<2^{n-1}}(-1)^{|I\cap (J+2^{n-1})|}a_{J+2^{n-1}}\\
&=\hat{f}_I+\sum_{0\le J<2^{n-1}}(-1)^{|I\cap J|}a_{J+2^{n-1}}
\text{ (注意 I 的范围)}\\
&=\hat{f}_I+\hat{g}_I\\
\end{aligned}
$$
$$
\begin{aligned}
\hat{a}_{I+2^{n-1}}(I<2^{n-1})&=\sum_{0\le J<2^n}(-1)^{|(I+2^{n-1})\cap J|}a_J\\
&=\sum_{0\le J<2^{n-1}}(-1)^{|(I+2^{n-1})\cap J|}a_J
+\sum_{2^{n-1}\le J<2^n}(-1)^{|(I+2^{n-1})\cap J|}a_J\\
&=\sum_{0\le J<2^{n-1}}(-1)^{|I\cap J|}a_J
+\sum_{0\le J<2^{n-1}}(-1)^{|(I+2^{n-1})\cap (J+2^{n-1})|}a_J\\
&=\hat{f}_I+\sum_{0\le J<2^{n-1}}(-1)^{|I\cap J|+1}a_J\\
&=\hat{f}_I-\hat{g}_I\\
\end{aligned}
$$
证毕。
-----------
然后说明 $\mathrm{DWT}(a\oplus b)=\mathrm{DWT}(a)\cdot \mathrm{DWT}(b)$。
证明：
**引理**：$(-1)^{|I\oplus J|}=(-1)^{|I|}\cdot (-1)^{|J|}$。
比较显然，因为异或后受到影响的只有同时在 $I,J$ 中的元素，左边会让它们的影响变成 $1$，而右边在 $I,J$ 中各算一个 $-1$，乘起来还是 $1$。
**证明**：
$$
\begin{aligned}
\hat{c_X}&=\sum_{I}(-1)^{|I\cap X|}\sum_{J\oplus K=I}a_J\cdot b_K\\
&=\sum_{J,K}(-1)^{|X\cap(J\oplus K)|}a_Jb_K\\
&=\sum_{J,K}(-1)^{|(J\cap X)\oplus(K\cap X)|}a_Jb_K\\
&=\sum_{J,K}(-1)^{|J\cap X|}a_J\cdot (-1)^{|K\cap X|}b_K\\
&=\sum_{J}(-1)^{|J\cap X|}a_J\cdot \sum_{K}(-1)^{|K\cap X|}b_K\\
&=\hat{a_X}\cdot \hat{b_X}
\end{aligned}
$$
# 【深入理解】
可能会觉得 DMT, DWT 的式子比较生硬，于是我们深入理解一下这两个东西到底在干嘛。
**DFT 是在做点值，DMT 和 DWT 其实也是在做另一种意义上的点值。**
具体来说，我们需要用到**集合幂级数**。
对于一个序列 $a_0\sim a_N$，定义一个多元多项式 $A(x_1\sim x_n)=\sum_{0\le I<2^{n}}a_I\cdot x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}$，其中 $i_1\sim i_n$ 是 $I$ 这个集合的二进制表示。
这个多项式有 $2^n$ 项，每一项的系数就是 $a$。这个 $A$ 叫做**集合幂级数**。可以类比序列对应到 OGF 上。简记 $A(x_1\sim x_n)=\sum_{0\le I<2^{n}}a_I\cdot x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}$ 为 $A(x)=\sum_{I}a_Ix^I$。
---
看看 DMT 是在干嘛。令 $J=(j_1,\dots,j_n)\in \{0,1\}^n$，即一个集合。
注意到当 $I\not\subseteq J$，存在 $i_t=1,j_t=0$，此时有 $j_t^{i_t}=0$，所以 $j_1^{i_1}\cdots j_n^{i_n}=0$。
而 $I\subseteq J$ 时，$(i_t,j_t)=(0,0)/(0,1)/(1,1)$，$j_t^{i_t}=1$，所以 $j_1^{i_1}\cdots j_n^{i_n}=1$。
因此，$A(J)=\sum_{I\subseteq J}a_I=\overline{a}_J$。
所以 DMT 计算 $\overline{a}$ 实际上是求出了 $A$ 在 $\{0,1\}^n$ 这 $2^n$ 个点处的值。
----
再看看 DWT 是在干嘛。令 $J=(j_1,\dots,j_n)\in \{0,1\}^n$，即一个集合。
那么 $P=((-1)^{j_1},(-1)^{j_2},\dots,(-1)^{j_n})\in \{-1,1\}^n$。
$$
\begin{aligned}
A(P)&=\sum_{0\le I< 2^n}a_I(-1)^{i_1j_1}(-1)^{i_2j_2}\cdots (-1)^{i_nj_n}\\
&=\sum_{0\le I<2^n}a_I(-1)^{i_1j_1+\cdots+i_nj_n}\\
&=\sum_{0\le I<2^n}a_I(-1)^{I\cdot J}
\end{aligned}
$$
**注**：向量 $a,b$ 的点乘 $a\cdot b=\sum a_ib_i$。上面 $i\cdot j$ 实际上是把 $i,j$ 两个集合看作了向量（或者说 01 串）进行运算。
而 $i\cdot j$ 在某一位上取 $1$，当且仅当这一位上 $i,j$ 都是 $1$，所以：
$$
\begin{aligned}
A(P)=\sum_{0\le I<2^n}a_I\cdot (-1)^{|I\cap J|}=\hat{a}_J
\end{aligned}
$$
所以 DWT 实际上是求出了 $A$ 在 $\{-1,1\}^n$ 这 $2^n$ 个点处的值。
总之，FFT, FMT, FWT 都是在先点值后插值。
# 例题
经验：**什么涉及位运算，什么就作为集合幂级数的指数。**
例如要求一些东西的与等于 $p$，放到集合幂级数的指数上，定位乘法为与卷积后，答案就是 $x^p$ 的系数。
## Nim (Topcoder 11469)
问有多少序列 $(i_1\sim i_m)$ 满足：
1. $i_1\oplus\cdots\oplus i_m=0$。
2. $1\le i_j\le k$。
3. $i_j$ 为质数。
$m\le 10^9,k\le 50000$。
---
构造一个序列 $a_0\sim a_{65536}$，使 $a_I=1\iff 1\le I\le K,I\in Prime$。
构造一个集合幂级数 $A(x)=\sum a_Ix^I$。
在乘法定义为异或卷积（$a_Ix^I\cdot b_Jx^J=a_Ib_Jx^{I\oplus J}$）时，$A^m(x)$ 中 $x^0$ 的系数就是答案。
那 $A^m(x)$ 怎么算？
$$
\begin{aligned}
A^{(m)}(x)&=\mathrm{iDWT}(\mathrm{DMT}(A^{(m)}(x))\\
&=\mathrm{iDMT}((\mathrm{DMT}(A(x))^m)\\
\end{aligned}
$$
因此只要做一次 $\mathrm{DMT}$，然后让所得序列的每一项变成 $m$ 次方，再做一次 $\mathrm{iDMT}$ 即可。注意这里是点乘 $m$ 次不是卷积 $m$ 次。
这题可以类比多项式快速幂：$f^m(x)=\exp \ln f^m(x)=\exp m\ln f(x)$。
## CF449D
给定 $a_1\sim a_n$，计数 $(1\le i_1<\cdots<i_k\le n)$，使 $a_{i_1}\,\mathrm{and}\,a_{i_2}\,\mathrm{and}\cdots\mathrm{and}\,a_{i_k}=0$。
$n,a_i\le 10^6$。
---
考虑取 $u=2^{20}-1$。定义集合幂级数 $F(x)=\prod(x^{a_i}+x^u)$。这里 $x^{a_i}$ 和 $x^u$ 都是集合幂级数，$u$ 相当于全集。也就是说，令 $A(x)=\sum_{I}[I=a_i]x^I,U(x)=\sum_{U}[I=U]x^I$，则 $x^{a_i}+x^u=A(x)+U(x)$。
令乘法为与卷积，答案就是 $F(x)$ 中 $x^0$ 的系数。这也说明为什么取 $u=2^{20}-1$，因为全集是与运算的单位元。
问题转化为求 $[x^0]F(x)$。令 $\mathrm{DMT'}$ 为与卷积的点值。
$F(x)=\mathrm{iDMT'}(\mathrm{DMT'}(x^{a_1}+x^u)\cdots \mathrm{DMT'}(x^{a_n}+x^u))$。注意在做了 $\mathrm{DMT'}$ 后的乘法是点乘。
注意到 $x^{a_i}+x^u$ 每一项的系数只有在 $a_i,u$ 处才取 $1$，其余为 $0$。
所以做 $\mathrm{DMT'}$ 后，每一项系数为 $1/2$。当 $I\subseteq a_i$ 时为 $2$，其余为 $1$。（$\check{a}_I=\sum_{I\subseteq J}a_J$）
这有什么用呢？记 $\check{S}_I=(\prod (x^{a_i}+x^u))_I$，有 $\check{S}_I=2^{t_I}$，其中 $t_I$ 表示 $a_1\sim a_n$ 中包含 $I$ 的个数。
那么问题转化为求 $t_0\sim t_{2^n-1}$，即给定一些集合，求每个集合被多少个包含。这也是 SOSDP 能做的。如果要类比 $\mathrm{DMT'}$，令 $cnt(J)$ 为 $a_1\sim a_n$ 中 $J$ 的个数。则 $t_I=\sum_{I\subseteq J}cnt(J)$，也是后缀和。
那么这一题就做完了，复杂度 $O(20\cdot 2^{20})$ 求 $t_0\sim t_{2^n-1}$，然后 $O(20\cdot 2^{20})$ 做一次 $\mathrm{iDMT'}$ 得到 $F(x)$，答案取 $x^0$ 系数。