k-FWT/n-DFT

· · 算法·理论

本文是我重温集合幂级数自己思考得到的一些鄙见。

总所周知，DFT 是在做 1 位的 2^k 进制数的不进位加法卷积。

FWT 是在做 n 位的 2 进制数的不进位加法卷积。

考虑拓展到 n 位 k 进制数的半加循环卷积。

分析 DFT 的本质，乘范德蒙德矩阵，利用单位根实现循环卷积。

分析 FWT 的本质，插值和逆插值。（看到文末会发现这种理解是浅显的）

k-FWT

二进制下的 FWT 依靠这个式子：

[S=\varnothing]=\frac{1}{2^n}\sum_{T\sube U} (-1)^{|S\cap T|}

证明不难，略过。

接下来我们把 n 位 k 进制数视作 n 维向量，每一位 v_i \in [0,k)。

怎么直接由集合拓展上面的式子到向量？

$2^n$ 实际上是枚举所有向量产生的系数，所以是 $k^n$。 $|S\cap T|=\sum_{i=0}^n S_{i}T_{i}$，也就是向量内积。 那 $-1$ 呢，就是 $\omega_2^1=\omega_k^1$。 猜测： $$ [S=0]=\frac{1}{k^n}\sum_T \omega_k^{\sum_i S_iT_i} $$ 证明： 当 $S=0$，求和始终为 $\omega_k^0=1$，显然正确。 否则考察 $S_p \ne 0$，变形原式。 $$ \begin{aligned} [S=0]&=\frac{1}{k^n}\sum_T \omega_k^{\sum_i S_iT_i}\\ &=\frac{1}{k^n}\sum_T \prod_i \omega_k^{S_iT_i}\\ \end{aligned} $$ 我们把 $T$ 除了第 $p$ 位，其余位都相同的 $T$ 分为一类。直接枚举 $n-1$ 维向量 $T'$，再考虑 $T_p=j$。 $$ \begin{aligned} [S=0]&=\frac{1}{k^n}\sum_T \prod_i \omega_k^{S_iT_i}\\ &=\frac{1}{k^n}\sum_{T'} \sum_{j=0}^{k-1} \prod_{i=0}^n \omega_{k}^{S_iT_i}\\ &=\frac{1}{k^n}\sum_{T'} (\sum_{j=0}^{k-1} \omega_k^{S_pj}) \prod_{i\ne p} \omega_{k}^{S_iT_i}\\ &=\frac{1}{k^n}\sum_{T'} \frac{\omega_k^{S_pk}-1}{\omega_k^{S_p}-1} \prod_{i\ne p} \omega_{k}^{S_iT_i}\\ &=0 \end{aligned} $$ （等比数列变形利用了 $S_p\ne 0 \Rightarrow \omega_k^{S_p} \ne 1$） 证毕。 根据这个性质，记 $f$ 是“向量幂级数”，理所当然的有它的沃尔什变换。 $$ \hat{f}_S=\sum_T \omega_k^{\sum_i S_iT_i} f_T $$ 以及逆变换。 $$ f_S=\frac{1}{k^n} \sum_T \omega_k^{\sum_i S_iT_i} \hat{f}_T $$ 然后你的半加循环卷积理论上来讲就可以直接在沃尔什变换后的“向量幂级数”上点乘，最后逆变换回去。 ### 2-FWT 那原理是什么呢？ 回顾集合幂级数的 FWT，找共通处类比。 一个集合幂级数 $f=\sum_S f_Sx^S$。 有一种表达方式是令 $x^S=\sum_{i\in S} x_i$。 然后把 $f$ 视作一个 $n$ 元多项式。 那么 FWT 一种理解方式是，对于一个集合 $S$，我们定义特征向量 $v(S)=((-1)^{[1\in S]},(-1)^{[2\in S]},\cdots,(-1)^{[n\in S]})$。即 $v(S)_i=(-1)^{[i\in S]}$。 然后对于每个集合，我们把每个元 $x_i=v(S)_i$ 代入这个 $n$ 元多项式求值，并把求值结果记作 $\hat{f}_S$。 你会发现 $f_T$ 对 $\hat{f}_S$ 的贡献系数恰好是 $(-1)^{|S\cap T|}$。 所以 FWT 可以理解为代入特征向量插值。 又为什么是这个特征向量呢？ 发现 $(-1)^x\cdot(-1)^y=(-1)^{(x+y)\bmod 2}=(-1)^{x\oplus y} 联系我们每一位的贡献独立，这个性质实际上是在指数上实现了 $1$ 位 $2$ 进制数的半加。 倘若对 $n$ 位都附上权，就能实现 $n$ 位的半加。 每一位是 $v(S)_i=(-1)^{[i\in S]}=(-1)^{S_i}$，于是 $v(S)_i\cdot v(T)_i=(-1)^{S_i}\cdot (-1)^{T_i}=(-1)^{S_i\oplus T_i}=v(S\oplus T)_i$。 用占位符的乘法描述出来就是： $x^S\cdot x^T=(\prod_{i\in S} x_i) (\prod_{i\in T} x_i)=\prod x_i^{S_i+T_i}=\prod x_i^{S_i \oplus T_i}=x^{S\oplus T}$。 （第二个等号到第三个等号利用了 $x_i$ 是 $-1$ 的幂） 经过 FWT 的插值后，$S$ 和 $T$ 的系数卷积恰好贡献到 $S\oplus T$。 ### k-FWT 原理 确保透彻理解上述内容后，开始拓展。 第一步，如何将集合幂级数拓展为“向量幂级数”？ 很简单，集合幂级数时 $x^S=\prod_{i\in S} x_i$。 实际上是 $x^S=\prod x_i^{S_i}$，那你类似的拓展，让单个元指数的范围扩到 $[0,k-1]$。 这样向量幂级数可以被描述为 $n$ 元 $k$ 次多项式（每一个元是 $[0,k-1]$ 次）。它包含了 $k^n$ 项，每一项能与每一个 $n$ 位 $k$ 进制数一一对应。 第二步，如何延用特征向量，以满足 $x^S\cdot x^T=x^{S \oplus T}$？ $k$ 进制半加就是 $\bmod k$ 意义下的循环卷积。 $2$ 进制我们使用 $(-1)$ 的幂来在指数上实现 $\bmod 2$。 同样的，我们使用 $k$ 次单位根安排特征向量，令 $v(S)_i=\omega_k^{S_i}$。 因为 $\omega_k^x\cdot \omega_k^y=\omega_k^{x+y\bmod k}$，所以： $x^S\cdot x^T=\prod x^{S_i+T_i\bmod k}=x^{S\oplus T}$。 于是成立，用这样的特征向量插值是正确的。 回顾前面那个式子： $$ \hat{f}_S=\sum_T \omega_k^{\sum_i S_iT_i} f_T $$ 当你代入 $v(S)$ 插值时，第 $T$ 项的系数贡献？ $$ f_Tx^T=f_T\prod x_i^{T_i}=f_T\prod v(S)_i^{T_i}=f_T\prod \omega_k^{S_iT_i} $$ 我们用更本质的做法推导出了 $k$ 进制下的沃尔什变换。 ### 实现 实现上呢，你对每一位贡献系数单独计算（增量法），就是利用下面这个式子： $$ \begin{aligned} \hat{f}_S&=\sum_{T'} (\sum_{j=0}^{k-1} \omega_k^{S_pj}) \prod_{i\ne p} \omega_{k}^{S_iT_i} f_T\\ \end{aligned} $$ 按上面这个式子直接做，分析一下时间复杂度应该是 $O(nk^{n+1})$。会这个结合一点分圆多项式的知识就能去水掉 CF1103E Radix sum。 但你发现对于一个 $p$ 不是实际上时按 $T'$ 分类，然后一类里乘范德蒙德矩阵，线性变换得到 $\hat{f}_S$ 吗？ 所以照搬个 DFT 过来把范德蒙德矩阵那部分从 $O(k^2)$ 降到 $O(k\log k)$。 所以 FWT 又有一种理解是对每个位都做一次 DFT。这又能解释为什么 FWT 是插值了。总有一种所学知识又串联起来，大道至简的感觉。 总时间复杂度做到 $O(nk^n\log k)$，也是我会的最优时间复杂度。不知道能不能更优。 单位根牛逼，点值表示牛逼。 线性代数牛逼，虽然我不会。