C++分裂基FFT代码

以下是C++实现的分裂基FFT代码：

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

const double pi = acos(-1);
const int maxn = 1 << 20;

struct Complex {
    double x, y;
    Complex(double _x = 0, double _y = 0) { x = _x, y = _y; }
    Complex operator + (const Complex &b) const { return Complex(x + b.x, y + b.y); }
    Complex operator - (const Complex &b) const { return Complex(x - b.x, y - b.y); }
    Complex operator * (const Complex &b) const { return Complex(x * b.x - y * b.y, x * b.y + y * b.x); }
} a[maxn], b[maxn], c[maxn];

void FFT(Complex *A, int len, int type) {
    for (int i = 1, j = 0; i < len; i++) {
        int bit = len >> 1;
        while (j >= bit) j -= bit, bit >>= 1;
        j += bit;
        if (i < j) swap(A[i], A[j]);
    }
    for (int h = 2; h <= len; h <<= 1) {
        Complex wn(cos(2 * pi / h), sin(type * 2 * pi / h));
        for (int j = 0; j < len; j += h) {
            Complex w(1, 0);
            for (int k = j; k < j + h / 2; k++) {
                Complex u = A[k], t = w * A[k + h / 2];
                A[k] = u + t, A[k + h / 2] = u - t, w = w * wn;
            }
        }
    }
    if (type == -1) for (int i = 0; i < len; i++) A[i].x /= len;
}

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

其中，FFT函数实现的是分裂基FFT算法。参数A表示待变换的复数数组，len表示数组长度，type表示变换类型，type=1表示正向变换，type=-1表示逆向变换。在正向变换时，首先进行蝴蝶变换，然后按照长度为2、4、8、...、len的子序列进行迭代，每次迭代使用旋转因子计算出一组长度为h的系数。在逆向变换时，需要对变换后的结果进行归一化，即将每个元素除以len。