K 进制 FWT
徐晨轩✅
·
·
算法·理论
K 进制 FWT
引入
问题：给定长度为 k^n 的序列 A_i,B_i，求
C_i=\sum_{j \oplus k=i} A_j B_k
其中 \oplus 是任意一种 k 进制按位运算。
通用解法
我们希望定义变换
\hat{F}(i)=\sum_{j=0}^{k^n-1} w(i,j) F(j)
使得
\forall 0\le i<k^n:\hat{C}(i)=\hat{A}(i)\hat{B}(i)
展开后即
\begin{aligned}
&\sum_{j=0}^{k^n-1} \sum_{k=0}^{k^n-1}w(i,j\oplus k)A(j)B(k)\\
=&\sum_{j=0}^{k^n-1} w(i,j) C(j)\\
=&\sum_{j=0}^{k^n-1} w(i,j)A(j)\sum_{k=0}^{k^n-1} w(i,k)B(k)\\
=&\sum_{j=0}^{k^n-1} \sum_{k=0}^{k^n-1}w(i,j)w(i,k)A(j)B(k)
\end{aligned}
也就是只需要满足 w(i,j)w(i,k)=w(i,j\oplus k) 就可以满足上述条件。
对于一种 \oplus，我们需要构造合适的 w，使得可以给定 F 快速计算 \hat{F}，同时需要给定 \hat{F} 快速计算 F。一般地，我们选择的 w 都要满足如下条件：
W=\begin{bmatrix}
w{(0,0)} & \cdots & w{(0,k^n-1)} \\
\vdots & \ddots & \vdots \\
w{(k^n-1,0)} & \cdots & w{(k^n-1,k^n-1)}
\end{bmatrix}
下文中设其逆矩阵为：
W'=\begin{bmatrix}
w'{(0,0)} & \cdots & w'{(0,k^n-1)} \\
\vdots & \ddots & \vdots \\
w'{(k^n-1,0)} & \cdots & w'{(k^n-1,k^n-1)}
\end{bmatrix}
- 设 i,j 的 k 进制表示分别为 (i_{n-1}\dots i_0)_k,(j_{n-1}\dots j_0)_k，则下式成立。
w(i,j)=\prod_{t=0}^{n-1} w(i_t,j_t)
可以证明其逆 w' 也满足类似的性质：
w'(i,j)=\prod_{t=0}^{n-1} w'(i_t,j_t)
证明：
现有
\forall i,j: \sum_{k} w(i,k)w'(k,j)=[i=j]
则
\begin{aligned}
&\sum_{k}\left(\prod_t w(i_t,k_t)\right)\left(\prod_t w'(k_t,j_t)\right)
\\=&\sum_{k} \prod_t w(i_t,k_t)w'(k_t,j_t)
\\=& \prod_t \sum_{k_t} w(i_t,k_t)w'(k_t,j_t)
\\=& \prod_t [i_t=j_t]
\\=& [i=j]
\end{aligned}
得证。
快速进行变换及逆变换
对长为 k^n 的序列 A 求其变换 \hat{A}。根据定义和上述 w 的性质，有：
\begin{aligned}
\hat{A}(i)&=\sum_{t=0}^{k-1}\sum_{j=0}^{k^{n-1}-1} w(i,j)w(i,tk^{n-1})A(j+tk^{n-1})
\\&=\sum_{t=0}^{k-1}w(i,tk^{n-1})\sum_{j=0}^{k^{n-1}-1} w(i\mod k^{n-1},j)A(j+tk^{n-1})
\end{aligned}
可以发现后面是一个子问题，即为对 A 序列的 [j+tk^{n-1},j+(t+1)k^{n-1}) 部分作变换。可以递归求解。时间复杂度为 T(n)=kT(n-1)+O(k^n)，得 T(n)=O(n k^n)。
对长为 k^n 的序列 \hat{A} 求其逆变换 A。
把 A 看作一个列向量
\begin{bmatrix}
A(0)\\
\vdots\\
A(k^n-1)
\end{bmatrix}
则有
\hat{A}=W \times A
于是
W' \times \hat{A} = W' \times W \times A=A
所以使用 w' 进行正变换时的分治算法即可。
综上所述，对 A,B 分别求得其变换后的 \hat{A},\hat{B}，并求出 \hat{C}=\hat{A}\cdot\hat{B}，最后求 \hat{C} 的逆变换得到 C 即可解决本文的引入问题。时间复杂度为 O(n k^n)。
特例
注：下述的 i,j 均满足 0\le i,j<k。其它情况的 w,w' 都要按位计算后作积。
\oplus 为按位取 max
构造 w(i,j)=[i\ge j]。此时有
w'(i,j)=\begin{cases}
1, \quad&i=j\\
-1, \quad&i=j+1\\
0, \quad&i\ne j \land i\ne j+1
\end{cases}
\oplus 为按位取 min
构造 w(i,j)=[i\le j]。此时有
w'(i,j)=\begin{cases}
1, \quad&i=j\\
-1, \quad&i=j-1\\
0, \quad&i\ne j \land i\ne j-1
\end{cases}
\oplus 为不进位加法
构造 w(i,j)=\omega^{ij}（其中 \omega 为 k 次单位根）。此时有 w'(i,j)=\dfrac{\omega^{-ij}}{k}。