k维FWT
sqrtqwq
·
·
算法·理论
\text{Part1.} 从一个新的角度看 \text{FWT}
我们设 c(i,j) 为 A_j 对于 FWT[A]_i 的贡献的系数。那么我们重新描述 \text{FWT} 的变化过程。
FWT[A]_i = \sum^{n-1}_{i=0} c(i,j)A_j
Lemma：我们知道 c(i,j)c(i,k)=c(i,j \oplus k)。其中的 \oplus 为任意一种的运算。
Proof：我们知道\sum^{\frac{n-1}{2}}_{j=0}c(i,j)A_j + \sum^n_{j=\frac{n-1}{2}+1} c(i,j)A_j = \sum^{n-1}_{j=1}C(i,j)A_j。然后将其带入一个运算即可。
因为每一位都是独立的，所以我们只需要考虑构造 \begin{matrix} c(0,0) & c(0,1) \\ c(1,0) & c(1,1) \end{matrix} 这个矩阵就可以做 \text{FWT}。我们称这个矩阵为位矩阵。然后我们根据 c(i,j)c(i,k)=c(i,j \oplus k) 这个性质去构造这个矩阵即可。
\text{Part2.} 从 \text{FWT} 到 \text{k-FWT}
考虑 \text{FWT} 的本质。实际上就是对一个 n 维 \{0,1\} 向量对于每一位取 \max（或运算） 或 \min（与运算） 或者求和后 \mod 2（异或运算）。而答案就是一个 2^n - 1 维的向量。
此时我们将 \text{FWT} 从二维推拓展 k 维后会有什么区别？
\text{Part3. k-FWT} 的或运算和与运算
我们定义 k 进制下的两个数 x_{1,2\cdots,n},y_{1,2\cdots,n} 的位运算为 z_i =\max(x_i,y_i)。
那么我们考虑去构造位矩阵。我们知道 w(i,j)w(i,k) = w(i,\max(j,k))。为了方便构造我们钦定 \forall w(i,j) \in [0,1],j \le k。可得 w(i,j)w(i,k)=w(i,k)。
即每一行中所有 1 在所有 0 前面。那么我们就可以构造出矩阵：
1 & 0 & 0 & \cdots & 0 \\
1 & 1 & 0 & \cdots & 0 \\
\vdots & & & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 1
\end{matrix}
对于与运算，构造方法是类似的，这里不在展开。
\text{Part 4. k -FWT} 的 \text{xor} 运算
我们定义 k 进制下的两个数 x_{1,2\cdots,n},y_{1,2\cdots,n} 的 \text{xor} 运算为 z_i = (x_i + y_i) \mod k。
然后我们就有 w(i,y)w(i,z) = w(i,(y + z) \mod k)。然后我们发现当 w(i,y) = \omega_k^y 时，满足条件 w(i,y)w(i,z) = w(i,(y + z) \mod k)。
但是这样子的话所有数都相同，所以没有逆。我们考虑带入范德蒙德矩阵，那么可得：
\begin{bmatrix}
1 & 1 & 1 & ... & 1 \\
1 & \omega_k^1 & \omega_k^2 & ... & \omega_k^{k-1} \\
1 & \omega_k^2 & \omega_k^4 & ... & \omega_k^{2(k-1)} \\
... & ... & ... & ... & ...\\
1 & \omega_k^{k-1} & \omega_k^{2(k-1)} & ... & \omega_k^{(k-1)(k-1)} \\
\end{bmatrix}
此时依然满足条件。根据范德蒙德矩阵的性质，我们知道上面那个矩阵的逆就是
\frac{1}{k}
\begin{bmatrix}
1 & 1 & 1 & ... & 1 \\
1 & \omega_k^{-1} & \omega_k^{-2} & ... & \omega_k^{-(k-1)} \\
1 & \omega_k^{-2} & \omega_k^{-4} & ... & \omega_k^{-2(k-1)} \\
... & ... & ... & ... & ...\\
1 & \omega_k^{-(k-1)} & \omega_k^{-2(k-1)} & ... & \omega_k^{-(k-1)(k-1)} \\
\end{bmatrix}
但是 k 不一定是 2 的幂，所以在模意义下的单位根不一定存在。此时你发现一般的办法都不可以满足不能分解质因数这个条件例如你对于整体模 i^k-1，但是这个是可以被因式分解。于是这里我们引入分圆多项式。
我们定义分圆多项式为 \Phi_k(x)=\prod\limits_{1\le j\le n,\space j\bot k} (i-\omega_k^j)。其有两个性质：\Phi_k(i) 不能被因式分解和 \Phi_k(i) \mid (i^k-1)。
应为 \Phi_k(i) 不可以被因式分解，所以我们直接对于这个东西取模肯定没有问题。但是可能会超时，于是我们考虑先对 i^k-1 取模，最后再对 \Phi_k(i) 取模，此时这个东西的正确性也是有保证的。