C++语言实序列FFT算法

下面是C++语言实现序列FFT算法的示例代码：

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cd;

void fft(vector<cd> &a, bool invert) {
    int n = a.size();
    if (n == 1) return;

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

    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * M_PI / n * (invert ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; i < n/2; ++i) {
        a[i] = a0[i] + w * a1[i];
        a[i+n/2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i+n/2] /= 2;
        }
        w *= wn;
    }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n), fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; ++i)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; ++i)
        result[i] = round(fa[i].real());
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    vector<int> a = {4, 3, 2, 1};
    vector<int> b = {1, 2, 3, 4};
    vector<int> c = multiply(a, b);

    for (int i = 0; i < c.size(); ++i)
        cout << c[i] << " ";
    cout << endl;

    return 0;
}

该代码实现了序列FFT算法，并且提供了一个示例，可以进行两个多项式的乘法操作。其中，`fft`函数为实现FFT算法的主要函数，`multiply`函数为实现多项式乘法的函数。在进行多项式乘法时，需要先将多项式转换为复数数组，然后进行FFT变换，最后再将结果转换为整型数组。