K 进制 FWT / 高维多项式乘法 略记

· · 个人记录

最简单的问题： 二进制不进位加法卷积。 即已知向量 A,B，求向量 C 使得 C_i=\sum_{i=j \text{xor} k} A_jB_k。 将其转为点值表示，即构造 \text{FWT}(C)_i=\text{FWT}(A)_i\times \text{FWT}(B)_i。 可以用大家熟悉的 FWT 算法解决： 每次从中间劈开形成两个向量 a,b，令 a'=a+b,b'=a-b，然后递归下去。

上述问题可以转化为高维多项式乘法问题，比如二进制异或卷积，就相当于对于 \log_2 N 维的多项式，在第 i 维意义下完成两个 1 次多项式相乘对 x^2-1 取模的运算。（又叫循环卷积）

根据 DFT 的线性性，容易知道多维的 DFT 问题可以逐维求解。

说人话，就是做 d 维的 DFT，可以考虑完成 d-1 维的 DFT 之后，对 k 个 d-1 维向量做一次长度 k 的 DFT（其中 k 是向量第 d 维的大小）。

容易实现一个每维长度都等于 k 的 DFT 如下：

void DWT(Cp *a) // 也叫 K 进制不进位加法卷积；K 进制 FWT
{
    static Cp t[10];
    for(int d = 1; d < M; d = d * V) // 从低维向高维做
        for(int i = 0; i < M; i += d * V)
            for(int j = 0; j < d; ++j) // 枚举向量的第 j 位
            {
                for(int k = 0; k < V; ++k) // n^2 跑 dft
                {
                    t[k] = Cp();
                    for(int p = 0; p < V; ++p)
                        t[k] = t[k] + a[i + j + p * d] * w[p * k];
                }
                for(int k = 0; k < V; ++k)
                    a[i + j + k * d] = t[k];
            }
}

考虑若每一维长度有所不同，并不影响该算法的运行。 考虑进行高维 DFT 的复杂度： 对于第 i 维，令该维大小为 k_i， 设 N=\prod k_i； 对于第 i 维，我们相当于要完成 n\over k_i 次长度为 k_i 的 DFT 运算。 容易用 bluestein-algorithm 将 DFT 的复杂度优化至 O(k_i\log k_i)。 算法时间复杂度 O(N\sum log_{k_i})= O(N\log N)。

归程

Radix Sum

算力训练大毒瘤！