编程fft

FFT（快速傅里叶变换）是一种用于计算离散傅里叶变换（DFT）的快速算法。以下是一个C++实现FFT的示例代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20; // N必须是2的次幂
const double PI = acos(-1.0);
struct Complex {
    double real, imag;
    Complex operator+(const Complex& other) const {
        return {real + other.real, imag + other.imag};
    }
    Complex operator-(const Complex& other) const {
        return {real - other.real, imag - other.imag};
    }
    Complex operator*(const Complex& other) const {
        return {real * other.real - imag * other.imag, real * other.imag + imag * other.real};
    }
};
Complex a[N], b[N], c[N];
int rev[N];
void fft(Complex* a, int n, int inv) {
    for (int i = 0; i < n; i++) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        int mid = len / 2;
        Complex w1 = {cos(2 * PI / len), inv * sin(2 * PI / len)};
        for (int j = 0; j < n; j += len) {
            Complex wk = {1, 0};
            for (int k = j; k < j + mid; k++) {
                Complex x = a[k], y = wk * a[k + mid];
                a[k] = x + y, a[k + mid] = x - y;
                wk = wk * w1;
            }
        }
    }
    if (inv == -1) {
        for (int i = 0; i < n; i++) {
            a[i].real /= n;
            a[i].imag /= n;
        }
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].real;
    }
    int len = 1, l = 0;
    while (len < n * 2) {
        len <<= 1;
        l++;
    }
    for (int i = 0; i < len; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
    fft(a, len, 1);
    for (int i = 0; i < len; i++) {
        a[i] = a[i] * a[i];
    }
    fft(a, len, -1);
    for (int i = 0; i < n; i++) {
        cout << (int)(a[i].real + 0.5) << " ";
    }
    return 0;
}

这是一个简单的FFT实现，可以用于计算两个多项式的乘积。在这个例子中，输入n表示多项式的项数，然后读取n个实数作为第一个多项式的系数，计算它的平方，并输出结果。请注意，N必须是2的次幂，否则需要补零。