浅谈 FWT
ZnPdCo
·
·
题解
我们先速通一下前面的部分：
按位或
A=\text{merge}(A_0, A_0+A_1)
a=\text{merge}(a_0, a_1-a_0)
按位与
A=\text{merge}(A_0+A_1, A_1)
a=\text{merge}(a_0 - a_1, a_1)
按位异或
A=\text{merge}(A_0+A_1, A_0-A_1)
a=\text{merge}(\frac{a_0+a_1}{2}, \frac{a_0-a_1}{2})
我们设 c(i,j) 是 a_j 对 A_i 的贡献系数。我们可以重新描述 FWT 变换的过程：
A_i = \sum_{j=0}^{n-1} c(i,j) a_j
因为有：
A_iB_i=C_i
所以我们可以通过简单的证明得到：c(i,j)c(i,k)=c(i,j\odot k)。其中 \odot 是任意一种位运算。
同时，c 函数还有一个重要的性质，它可以按位处理。
举个例子，我们变换的时候：
A_i = \sum_{j=0}^{n-1} c(i,j) a_j
这么做是比较劣的，我们将其拆分：
A_i = \sum_{j=0}^{(n-1)/2} c(i,j) a_j+\sum_{j=(n-1)/2+1}^{n-1} c(i,j) a_j
考虑前面的式子和后面的式子 i,j 的区别，发现只有最高位不同。
所以我们将 i,j 去除最高位的值为 i',j'，并记 i_0 为 i 的最高位。有：
A_i = c(i_0,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(i_0,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
如果 i_0=0，则有：
A_i = c(0,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(0,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
$$
A_i = c(1,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(1,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
$$
也就是说，我们只需要：
$$
\begin{bmatrix}
c(0,0) & c(0,1) \\
c(1,0) & c(1,1)
\end{bmatrix}
$$
四个数就可以完成变换了。我们称这个矩阵为位矩阵。
---
如果我们要进行逆变换，则需要上面的位矩阵的逆矩阵。
若逆矩阵为 $c^{-1}$，可以通过类似操作得到原数：
$$
a_i = \sum_{j=0}^n c^{-1}(i,j) A_j
$$
逆矩阵不一定存在，比如如果有一排 $0$ 或者一列 $0$ 那么这个矩阵就没有逆，我们在构造时需要格外小心。
### 按位或
我们可以构造：
$$
\begin{bmatrix}
1 & 0 \\
1 & 1
\end{bmatrix}
$$
这样满足 $c(i,j)c(i,k)=c(i,j\cup k)$。我们发现，这和我们前面推出的 $A=\text{merge}(A_0, A_0+A_1)$ 一模一样！同理，下面也是一个满足这个条件的矩阵，但我们一般使用上面这个：
$$
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
$$
虽然下面这个矩阵也满足 $c(i,j)c(i,k)=c(i,j\cup k)$，但这个矩阵存在一排 $0$，不存在逆，所以不合法：
$$
\begin{bmatrix}
0 & 0 \\
1 & 1
\end{bmatrix}
$$
如果我们要进行逆变换，则需要对矩阵求逆，以**最上面**这个矩阵为例，得：
$$
\begin{bmatrix}
1 & 0 \\
-1 & 1
\end{bmatrix}
$$
然后按照顺变换的方法，把逆变换矩阵代入即可。
### 按位与
我们可以构造：
$$
\begin{bmatrix}
1 & 1 \\
0 & 1
\end{bmatrix}
$$
这样满足 $c(i,j)c(i,k)=c(i,j\cap k)$。
逆矩阵：
$$
\begin{bmatrix}
1 & -1 \\
0 & 1
\end{bmatrix}
$$
### 按位异或
我们可以构造：
$$
\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
$$
这样满足 $c(i,j)c(i,k)=c(i,j\oplus k)$。
逆矩阵：
$$
\begin{bmatrix}
0.5 & 0.5 \\
0.5 & -0.5
\end{bmatrix}
$$
## K 维 FWT
其实位运算的本质是对一个 $n$ 维 $\{0,1\}$ 向量的运算。或运算就是每一维取 $\max$。且运算就是每一维取 $\min$。异或运算则是每一维对应相加再 $\bmod 2$。
位运算有个特点：向量的每一位都是独立的。
我们把 $\{0,1\}$ 扩展到 $[0,K)\cap Z$ 也就是扩展到 $K$ 进制，看看会得到什么？
### max 运算
我们将 $\cup$ 运算拓展到 $K$ 进制，定义 $i\cup j$ 表示按位取 $\max$，有：
$$
c(i,j)c(i,k)=c(i,j\cup k)
$$
若 $j=k$，那么上式又是：
$$
c(i,j)c(i,j)=c(i,j)
$$
也就是说，每一行的 $1$ 必定只能在 $0$ 的前面，如果在后面则不合法了。手玩一下可以发现一组合法构造：
$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1
\end{bmatrix}
$$
求逆可得：
$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
-1 & 1 & 0 & 0 \\
0 & -1 & 1 & 0 \\
0 & 0 & -1 & 1
\end{bmatrix}
$$
### min 运算
我们将 $\cap$ 运算拓展到 $K$ 进制，定义 $i\cap j$ 表示按位取 $\min$，有：
$$
c(i,j)c(i,k)=c(i,j\cap k)
$$
若 $j=k$，那么上式又是：
$$
c(i,j)c(i,j)=c(i,j)
$$
也就是说，每一行的 $1$ 必定只能在 $0$ 的后面，如果在前面则不合法了。手玩一下可以发现一组合法构造：
$$
\begin{bmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$
求逆可得：
$$
\begin{bmatrix}
1 & -1 & 0 & 0 \\
0 & 1 & -1 & 0 \\
0 & 0 & 1 & -1 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$
前两者用得比较少，用得比较多的是：
### 不进位加法
我们将 $\oplus$ 运算拓展到 $K$ 进制，定义 $i\oplus j$ 表示按位相加再 $\bmod K$，有：
$$
c(i,j)c(i,k)=c(i,j\oplus k)
$$
我们构造 $c(i,j)=\omega_{K}^j$，就可以满足要求了：
$$
\omega_{K}^j\omega_{k}^k=\omega_{K}^{(j+k)\bmod K}
$$
但是每一行都一样矩阵也没有逆，所以我们可以构造 $c(i,j)=\omega_{K}^{(i-1)j}$ 即可。
有下面这个矩阵：
$$
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega_{K}^1 & \omega_{K}^2 & \cdots & \omega_{K}^{k-1} \\
1 & \omega_{K}^2 & \omega_{K}^4 & \cdots & \omega_{K}^{2(k-1)} \\
1 & \omega_{K}^3 & \omega_{K}^6 & \cdots & \omega_{K}^{3(k-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega_{K}^{k-1} & \omega_{K}^{2(k-1)} & \cdots & \omega_{K}^{(k-1)(k-1)}
\end{bmatrix}
$$
此即为 [范德蒙德矩阵](https://en.wikipedia.org/wiki/Vandermonde_matrix)，求逆可得：
$$
\frac{1}{K}\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega_{K}^{-1} & \omega_{K}^{-2} & \cdots & \omega_{K}^{-(k-1)} \\
1 & \omega_{K}^{-2} & \omega_{K}^{-4} & \cdots & \omega_{K}^{-2(k-1)} \\
1 & \omega_{K}^{-3} & \omega_{K}^{-6} & \cdots & \omega_{K}^{-3(k-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega_{K}^{-(k-1)} & \omega_{K}^{-2(k-1)} & \cdots & \omega_{K}^{-(k-1)(k-1)}
\end{bmatrix}
$$
如果我们题目给出的模数是存在单位根的，我们就可以简单实现。
---
但是**单位根在模意义下可能不存在**，所以我们考虑扩域，就是人为地定义一个 $x$，满足 $x^K=1$，然后直接把 $x$ 代入计算，这样每个数都是一个关于 $x$ 的 $k-1$ 次多项式。我们只需要在 $\pmod {x^K-1}$ 下计算即可。那么矩阵可以这么表示：
$$
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & x^1 & x^2 & \cdots & x^{k-1} \\
1 & x^2 & x^4 & \cdots & x^{2(k-1)} \\
1 & x^3 & x^6 & \cdots & x^{3(k-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & x^{k-1} & x^{2(k-1)} & \cdots & x^{(k-1)(k-1)}
\end{bmatrix}
$$
但是这么做可能会存在零因子，也就是**一个数有多种表示方法**，我们无法确定一个数的真实值。
我们考虑不 $\pmod {x^K-1}$ 了，我们 $\bmod$ 分圆多项式 $\Phi_{K}(x)$，他满足 $x$ 的阶为 $k$，且在 $Q$ 上不可约。所以我们定义上面的计算是在 $\pmod {\Phi_{K}(x)}$ 下进行即可。
另一方面，如何求分圆多项式，这一点可以在[因式分解](https://www.luogu.com.cn/problem/P1520)这道题的题解区里了解。这里给出分圆多项式的表：
还有一个问题是，$\bmod \Phi_{K}(x)$ 常数大（因为 $\Phi$ 本身就是一个多项式）。但是因为 $\Phi_{K}(x)\mid x^k-1$，我们只需要在计算时 $\bmod x^k -1$，最后再 $\bmod \Phi_{K}(x)$ 即可。