与同学讨论之后顿悟了如何从 FWT 得到 FFT，神乎其神。
对于二进制异或卷积，我们设置 \(n\) 个变元 \(x_{0\sim n-1}\)，令 \(X^S=\prod\limits_{i\in S}x_i\)，做 \(n\) 元多项式乘法，根据二进制异或的运算表 \((1,1)\to0\)，得到这样做的充要条件 \(x_i^2=1\)，即在模 \((x_i^2-1)\) 意义下做多项式乘法。对 \((x_i^2-1)\) 因式分解得到 \((x_i+1)(x_i-1)\)，根据群论知识，相当于对 \(2^n\) 个点值代入后点乘，最后插值出来。
扩展到三进制，依然设置 \(n\) 个变元，每一位可能取到 \(x_i^0,x_i^1,x_i^2\)，要求 \(x_i^3=1\)。上三次单位根进行因式分解，得到 \((x_i-\omega_3^0)(x_i-\omega_3^1)(x_i-\omega_3^2)\)，将 \(3^n\) 个点值代入后点乘。作为例子，写一下转移矩阵：
于是我们得到 \(k\) 进制异或卷积的理论方法，利用 \(k\) 次单位根插值即可。每一位都是独立的，容易设计出 \(O(nk^{n+1})\) 的做法。具体来说就是每位存在一个转移矩阵，乘上这个矩阵进行转移即可。
好的，上面实际上讲述了多维 \(k\) 项式循环卷积的一般方法，我们尝试推广到一般多项式乘法。对于两个 \(n\) 次多项式相乘，我们可以认为其就是 \(N\) 项式循环卷积，其中 \(N>2n\)，这个卷积是一维的，直接类比上文，得到 \(x^N=1\)，使用 \(N\) 次单位根处理，但是直接矩阵乘向量是 \(O(N^2)\) 的。可以分治做到 \(O(N\log N)\)，那是纯粹的多项式技巧。
本文揭示了 FWT 和 FFT 之间的深刻联系，真是一篇不可多得的好文！其实我更好奇如何在群论视角下看这个东西，但好像群论水平低的令人发指。