快速傅里叶变换c++代码

以下是C++实现的快速傅里叶变换代码：

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

const double PI = acos(-1.0);

struct Complex {
    double r, i;
    Complex(double r = 0, double i = 0) : r(r), i(i) {}
    Complex operator+(const Complex &rhs) const {
        return Complex(r + rhs.r, i + rhs.i);
    }
    Complex operator-(const Complex &rhs) const {
        return Complex(r - rhs.r, i - rhs.i);
    }
    Complex operator*(const Complex &rhs) const {
        return Complex(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r);
    }
};

void FFT(Complex *a, int n, int inv) {
    for (int i = 1, j = 0; i < n; ++i) {
        for (int s = n; j ^= s >>= 1, ~j & s;);
        if (i < j) swap(a[i], a[j]);
    }
    for (int m = 1; m < n; m <<= 1) {
        Complex wm(cos(PI / m), inv * sin(PI / m));
        for (int i = 0; i < n; i += m << 1) {
            Complex w(1, 0);
            for (int j = 0; j < m; ++j, w = w * wm) {
                Complex x = a[i + j], y = w * a[i + j + m];
                a[i + j] = x + y, a[i + j + m] = x - y;
            }
        }
    }
    if (inv == -1) {
        for (int i = 0; i < n; ++i) {
            a[i].r /= n;
        }
    }
}

const int N = 1 << 18;
Complex a[N], b[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; ++i) {
        scanf("%lf", &a[i].r);
    }
    for (int i = 0; i <= m; ++i) {
        scanf("%lf", &b[i].r);
    }
    int len = 1;
    while (len <= n + m) len <<= 1;
    FFT(a, len, 1), FFT(b, len, 1);
    for (int i = 0; i < len; ++i) {
        a[i] = a[i] * b[i];
    }
    FFT(a, len, -1);
    for (int i = 0; i <= n + m; ++i) {
        printf("%d ", (int)(a[i].r + 0.5));
    }
    return 0;}