用C++实现FFT算法

好的，下面是C++实现FFT算法的代码，供你参考：

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);

struct Complex {
    double a, b;
    Complex(double a = 0, double b = 0) : a(a), b(b) {}
    Complex operator+(const Complex &c) const {
        return Complex(a + c.a, b + c.b);
    }
    Complex operator-(const Complex &c) const {
        return Complex(a - c.a, b - c.b);
    }
    Complex operator*(const Complex &c) const {
        return Complex(a * c.a - b * c.b, a * c.b + b * c.a);
    }
};

const int MAXN = 1 << 20;
Complex a[MAXN], b[MAXN];

void fft(Complex *a, int n, int f) {
    if (n == 1) return;
    Complex a0[n / 2], a1[n / 2];
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }
    fft(a0, n / 2, f);
    fft(a1, n / 2, f);
    Complex wn(cos(2 * PI / n), sin(f * 2 * PI / n)), w(1, 0);
    for (int i = 0; i < n / 2; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        w = w * wn;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].a;
    }
    fft(a, n, 1);
    for (int i = 0; i < n; i++) {
        b[i] = a[i] * a[i];
    }
    fft(b, n, -1);
    for (int i = 0; i < n; i++) {
        cout << (int)(b[i].a / n + 0.5) << " ";
    }
    return 0;
}

这里实现了一个简单的FFT算法，可以输入一个长度为 $n$ 的实数序列 $a$，计算出其平方后的结果。

其中，复数类 `Complex` 重载了 `+`、`-` 和 `*` 运算符，方便实现复数的加减乘法。`fft` 函数是递归实现的，每次将输入的序列分成两半，然后递归计算每一半的FFT，最后将结果合并起来。在计算递归的过程中，用到了旋转因子 $w_n=\cos\frac{2\pi}{n}\pm i\sin\frac{2\pi}{n}$，可以通过递推计算出来，具体实现见代码。在计算 FFT 的过程中，需要注意实现正确的傅里叶变换和傅里叶逆变换。

实现 FFT 算法需要一定的数学知识和编程基础，如果需要更深入的了解可以参考相关的书籍和资料。