专栏文章

k-FWT/n-DFT

KKazamaRuri
算法·理论参与者 8已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
2 份
快照标识符
@mkbeujul
此快照首次捕获于
2026/01/13 01:02
上个月
此快照最后确认于
2026/02/19 01:20
16 小时前
查看原文
本文是我重温集合幂级数自己思考得到的一些鄙见。
总所周知，DFT 是在做 11 位的 2k2^k 进制数的不进位加法卷积。
FWT 是在做 nn 位的 22 进制数的不进位加法卷积。
考虑拓展到 nn 位 kk 进制数的半加循环卷积。
分析 DFT 的本质，乘范德蒙德矩阵，利用单位根实现循环卷积。
分析 FWT 的本质，插值和逆插值。（看到文末会发现这种理解是浅显的）

k-FWT

二进制下的 FWT 依靠这个式子：
[S=∅]=12n∑T⊆U(−1)∣S∩T∣[S=\varnothing]=\frac{1}{2^n}\sum_{T\sube U} (-1)^{|S\cap T|}
证明不难，略过。
接下来我们把 nn 位 kk 进制数视作 nn 维向量，每一位 vi∈[0,k)v_i \in [0,k)。
怎么直接由集合拓展上面的式子到向量？
∅\varnothing 实际上是 00 向量。
2n2^n 实际上是枚举所有向量产生的系数，所以是 knk^n。
∣S∩T∣=∑i=0nSiTi|S\cap T|=\sum_{i=0}^n S_{i}T_{i}，也就是向量内积。
那 −1-1 呢，就是 ω21=ωk1\omega_2^1=\omega_k^1。
猜测：
[S=0]=1kn∑Tωk∑iSiTi[S=0]=\frac{1}{k^n}\sum_T \omega_k^{\sum_i S_iT_i}
证明：
当 S=0S=0，求和始终为 ωk0=1\omega_k^0=1，显然正确。
否则考察 Sp≠0S_p \ne 0，变形原式。
[S=0]=1kn∑Tωk∑iSiTi=1kn∑T∏iωkSiTi\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}
我们把 TT 除了第 pp 位，其余位都相同的 TT 分为一类。直接枚举 n−1n-1 维向量 T′T'，再考虑 Tp=jT_p=j。
[S=0]=1kn∑T∏iωkSiTi=1kn∑T′∑j=0k−1∏i=0nωkSiTi=1kn∑T′(∑j=0k−1ωkSpj)∏i≠pωkSiTi=1kn∑T′ωkSpk−1ωkSp−1∏i≠pωkSiTi=0\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}
（等比数列变形利用了 Sp≠0⇒ωkSp≠1S_p\ne 0 \Rightarrow \omega_k^{S_p} \ne 1）
证毕。
根据这个性质，记 ff 是“向量幂级数”，理所当然的有它的沃尔什变换。
f^S=∑Tωk∑iSiTifT\hat{f}_S=\sum_T \omega_k^{\sum_i S_iT_i} f_T
以及逆变换。
fS=1kn∑Tωk∑iSiTif^Tf_S=\frac{1}{k^n} \sum_T \omega_k^{\sum_i S_iT_i} \hat{f}_T
然后你的半加循环卷积理论上来讲就可以直接在沃尔什变换后的“向量幂级数”上点乘，最后逆变换回去。

2-FWT

那原理是什么呢？
回顾集合幂级数的 FWT，找共通处类比。
一个集合幂级数 f=∑SfSxSf=\sum_S f_Sx^S。
有一种表达方式是令 xS=∑i∈Sxix^S=\sum_{i\in S} x_i。
然后把 ff 视作一个 nn 元多项式。
那么 FWT 一种理解方式是，对于一个集合 SS，我们定义特征向量 v(S)=((−1)[1∈S],(−1)[2∈S],⋯ ,(−1)[n∈S])v(S)=((-1)^{[1\in S]},(-1)^{[2\in S]},\cdots,(-1)^{[n\in S]})。即 v(S)i=(−1)[i∈S]v(S)_i=(-1)^{[i\in S]}。
然后对于每个集合，我们把每个元 xi=v(S)ix_i=v(S)_i 代入这个 nn 元多项式求值，并把求值结果记作 f^S\hat{f}_S。
你会发现 fTf_T 对 f^S\hat{f}_S 的贡献系数恰好是 (−1)∣S∩T∣(-1)^{|S\cap T|}。
所以 FWT 可以理解为代入特征向量插值。
又为什么是这个特征向量呢？
发现 (−1)x⋅(−1)y=(−1)(x+y) mod 2=(−1)x⊕y(-1)^x\cdot(-1)^y=(-1)^{(x+y)\bmod 2}=(-1)^{x\oplus y}
⊕\oplus 是 kk 进制数半加。这里是 22 进制。
联系我们每一位的贡献独立，这个性质实际上是在指数上实现了 11 位 22 进制数的半加。
倘若对 nn 位都附上权，就能实现 nn 位的半加。
每一位是 v(S)i=(−1)[i∈S]=(−1)Siv(S)_i=(-1)^{[i\in S]}=(-1)^{S_i}，于是 v(S)i⋅v(T)i=(−1)Si⋅(−1)Ti=(−1)Si⊕Ti=v(S⊕T)iv(S)_i\cdot v(T)_i=(-1)^{S_i}\cdot (-1)^{T_i}=(-1)^{S_i\oplus T_i}=v(S\oplus T)_i。
用占位符的乘法描述出来就是：
xS⋅xT=(∏i∈Sxi)(∏i∈Txi)=∏xiSi+Ti=∏xiSi⊕Ti=xS⊕Tx^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}。
（第二个等号到第三个等号利用了 xix_i 是 −1-1 的幂）
经过 FWT 的插值后，SS 和 TT 的系数卷积恰好贡献到 S⊕TS\oplus T。

k-FWT 原理

确保透彻理解上述内容后，开始拓展。
第一步，如何将集合幂级数拓展为“向量幂级数”？
很简单，集合幂级数时 xS=∏i∈Sxix^S=\prod_{i\in S} x_i。
实际上是 xS=∏xiSix^S=\prod x_i^{S_i}，那你类似的拓展，让单个元指数的范围扩到 [0,k−1][0,k-1]。
这样向量幂级数可以被描述为 nn 元 kk 次多项式（每一个元是 [0,k−1][0,k-1] 次）。它包含了 knk^n 项，每一项能与每一个 nn 位 kk 进制数一一对应。
第二步，如何延用特征向量，以满足 xS⋅xT=xS⊕Tx^S\cdot x^T=x^{S \oplus T}？
kk 进制半加就是  mod k\bmod k 意义下的循环卷积。
22 进制我们使用 (−1)(-1) 的幂来在指数上实现  mod 2\bmod 2。
同样的，我们使用 kk 次单位根安排特征向量，令 v(S)i=ωkSiv(S)_i=\omega_k^{S_i}。
因为 ωkx⋅ωky=ωkx+y mod k\omega_k^x\cdot \omega_k^y=\omega_k^{x+y\bmod k}，所以：
xS⋅xT=∏xSi+Ti mod k=xS⊕Tx^S\cdot x^T=\prod x^{S_i+T_i\bmod k}=x^{S\oplus T}。
于是成立，用这样的特征向量插值是正确的。
回顾前面那个式子：
f^S=∑Tωk∑iSiTifT\hat{f}_S=\sum_T \omega_k^{\sum_i S_iT_i} f_T
当你代入 v(S)v(S) 插值时，第 TT 项的系数贡献？
fTxT=fT∏xiTi=fT∏v(S)iTi=fT∏ωkSiTif_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}
我们用更本质的做法推导出了 kk 进制下的沃尔什变换。

实现

实现上呢，你对每一位贡献系数单独计算（增量法），就是利用下面这个式子：
f^S=∑T′(∑j=0k−1ωkSpj)∏i≠pωkSiTifT\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(nkn+1)O(nk^{n+1})。会这个结合一点分圆多项式的知识就能去水掉 CF1103E Radix sum。
但你发现对于一个 pp 不是实际上时按 T′T' 分类，然后一类里乘范德蒙德矩阵，线性变换得到 f^S\hat{f}_S 吗？
所以照搬个 DFT 过来把范德蒙德矩阵那部分从 O(k2)O(k^2) 降到 O(klog⁡k)O(k\log k)。
所以 FWT 又有一种理解是对每个位都做一次 DFT。这又能解释为什么 FWT 是插值了。总有一种所学知识又串联起来，大道至简的感觉。
总时间复杂度做到 O(nknlog⁡k)O(nk^n\log k)，也是我会的最优时间复杂度。不知道能不能更优。
单位根牛逼，点值表示牛逼。
线性代数牛逼，虽然我不会。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...