前言：今天遇到各种烦心事，包括但不限于自己的企鹅号登不上去了,一堆高中摆烂人借着会考训练的名义在我训练的机房打游戏。
我直接跳过大部分步骤吧。
做一个类似于总结类的博客得了。
首先\(DFT\)是将一个多项式转为一个特定的点值表达的形式。
我们在复数域选取单位根作为点值的\(x\)。
有以下三个重要结论：
\(w_n^{n} = 1\)
\(w_n^{k} = w_{2n}^{2k}\)
\(w_{2n}^{k + n} = -w_{2n}^{k}\)
考虑我们在处理\(F(x)\)的\(DFT\)时
我们将其偶数和奇数位的系数单独提出来作为一个多项式\(G,H\)。
那么有\(F(x) = G(x^2) + x \times H(x ^ 2)\)。
那么对于\(DFT\)来说
\(DFT(F)_k(F(w_{n}^k)) = G((w_{n}^{k})^2) + w_n^{k} \times H((w_{n}^{k})^2)\\=G((w_{n}^{2k})) + w_n^{k} \times H((w_{n}^{2k}))\\=G((w_{n/2}^{k})) + w_n^{k} \times H((w_{n/2}^{k}))\\=DFT(G)_k + w_n^{k}\times DFT(F)_k\)
同理有
\(DFT(F)_{k + n / 2}(F(w_{n}^{k + n / 2})) = DFT(G)_k - w_n^{k}\times DFT(F)_k\)
递归FFT
#include <cmath>
#include <complex>
typedef std::complex<double> Comp; // STL complex
const Comp I(0, 1); // i
const int MAX_N = 1 << 20;
Comp tmp[MAX_N];
void DFT(Comp *f, int n, int rev) { // rev=1,DFT; rev=-1,IDFT
if (n == 1) return;
for (int i = 0; i < n; ++i) tmp[i] = f[i];
for (int i = 0; i < n; ++i) { // 偶数放左边，奇数放右边
if (i & 1)
f[n / 2 + i / 2] = tmp[i];
else
f[i / 2] = tmp[i];
}
Comp *g = f, *h = f + n / 2;
DFT(g, n / 2, rev), DFT(h, n / 2, rev); // 递归 DFT
Comp cur(1, 0), step(cos(2 * M_PI / n), sin(2 * M_PI * rev / n));
// Comp step=exp(I*(2*M_PI/n*rev)); // 两个 step 定义是等价的
for (int k = 0; k < n / 2; ++k) {
tmp[k] = g[k] + cur * h[k];
tmp[k + n / 2] = g[k] - cur * h[k];
cur *= step;
}
for (int i = 0; i < n; ++i) f[i] = tmp[i];
}
蝴蝶变换，等我被卡了我再来填这个坑。