FFT代码

以下是一个经典的 Cooley-Tukey 快速傅里叶变换（FFT）算法的 C++ 实现：

#include <complex>
#include <vector>

typedef std::complex<double> Complex;

std::vector<Complex> fft(std::vector<Complex> a) {
    int n = a.size();
    if (n == 1) return a;

    std::vector<Complex> a0(n / 2), a1(n / 2);
    for (int i = 0; i < n / 2; ++i) {
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    std::vector<Complex> y0 = fft(a0);
    std::vector<Complex> y1 = fft(a1);

    std::vector<Complex> y(n);
    for (int k = 0; k < n / 2; ++k) {
        Complex w = std::polar(1.0, -2 * M_PI * k / n) * y1[k];
        y[k] = y0[k] + w;
        y[k + n / 2] = y0[k] - w;
    }

    return y;
}

其中 `std::complex` 是 C++ STL 中的复数类，需要包含 `<complex>` 头文件。`std::polar` 是求极坐标的函数，第一个参数表示模长，第二个参数表示相角。