高维 DFT 算法（FWT 快速沃尔什变换）

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

上述问题可以转化为高维多项式乘法问题，即对于 (log 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) 维，我们相当于要完成 (nover k_i) 次长度为 (k_i) 的 DFT 运算。
容易用 bluestein-algorithm 将 DFT 的复杂度优化至 (O(k_ilog k_i))。
由于维数不超过 (log N)，因此算法复杂度存在上界 (O(Nlog^2 N))。