写一个快速傅里叶变换算法C++

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

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

const double PI = acos(-1);
const int MAXN = 1 << 17; // 最大长度，需要是 2 的整数次幂

int rev[MAXN]; // 位逆序置换数组
complex<double> f[MAXN], g[MAXN]; // 多项式

void fft(complex<double> *a, int n, int inv) {
    for (int i = 0; i < n; ++i)
        if (i < rev[i]) swap(a[i], a[rev[i]]); // 位逆序置换
    for (int i = 1; i < n; i <<= 1) { // 迭代次数
        complex<double> wn(cos(PI / i), inv * sin(PI / i)); // 单位复根
        for (int j = 0; j < n; j += i << 1) { // 块编号
            complex<double> w(1, 0);
            for (int k = j; k < j + i; ++k, w *= wn) { // 蝴蝶操作
                complex<double> x = a[k], y = w * a[k + i];
                a[k] = x + y, a[k + i] = x - y;
            }
        }
    }
    if (inv == -1)
        for (int i = 0; i < n; ++i) a[i] /= n; // 除以 n
}

int main() {
    int n = 8;
    for (int i = 0; i < n; ++i) {
        cin >> f[i];
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (int(log2(n)) - 1)); // 预处理位逆序置换
    }
    fft(f, n, 1); // DFT
    for (int i = 0; i < n; ++i) g[i] = f[i] * f[i]; // 平方
    fft(g, n, -1); // IDFT
    for (int i = 0; i < n; ++i) cout << (int)(g[i].real() + 0.5) << " "; // 四舍五入取整
    return 0;
}

其中 `fft` 函数实现了快速傅里叶变换，`main` 函数中的代码则展示了如何使用该函数进行多项式平方。