不使用vector实现FFTc++

FFT（快速傅里叶变换）是一种高效的算法，可以在O(nlogn)时间复杂度下计算离散傅里叶变换（DFT）。虽然使用vector实现FFT是比较常见的方法，但也可以使用数组实现FFT。

下面给出一个使用数组实现FFT的C++代码：

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

const double PI = acos(-1);

struct Complex {
    double real, imag;
    Complex() {}
    Complex(double r, double i): real(r), imag(i) {}
    inline Complex operator+(const Complex &c) const {
        return Complex(real + c.real, imag + c.imag);
    }
    inline Complex operator-(const Complex &c) const {
        return Complex(real - c.real, imag - c.imag);
    }
    inline Complex operator*(const Complex &c) const {
        return Complex(real * c.real - imag * c.imag, real * c.imag + imag * c.real);
    }
};

void FFT(Complex *a, int n, int flag) {
    for (int i = 1, j = 0; i < n; i++) {
        for (int k = n; j ^= k >>= 1, ~j & k;);
        if (i < j) swap(a[i], a[j]);
    }
    for (int m = 2; m <= n; m <<= 1) {
        Complex wm(cos(2 * PI / m), flag * sin(2 * PI / m));
        for (int k = 0; k < n; k += m) {
            Complex w(1, 0);
            for (int j = k; j < k + (m >> 1); j++, w = w * wm) {
                Complex u = a[j], t = w * a[j + (m >> 1)];
                a[j] = u + t, a[j + (m >> 1)] = u - t;
            }
        }
    }
    if (flag == -1) for (int i = 0; i < n; i++) a[i].real /= n;
}

void Convolution(int *a, int na, int *b, int nb, int *res) {
    static Complex A[1 << 21], B[1 << 21];
    int n = na + nb - 1, m = 1;
    while (m < n) m <<= 1;
    for (int i = 0; i < m; i++) {
        A[i] = i < na ? Complex(a[i], 0) : Complex(0, 0);
        B[i] = i < nb ? Complex(b[i], 0) : Complex(0, 0);
    }
    FFT(A, m, 1), FFT(B, m, 1);
    for (int i = 0; i < m; i++) A[i] = A[i] * B[i];
    FFT(A, m, -1);
    for (int i = 0; i < n; i++) res[i] = (int)(A[i].real + 0.5);
}

int main() {
    int a[] = {1, 2, 3, 4}, b[] = {5, 6, 7};
    int n = sizeof(a) / sizeof(int), m = sizeof(b) / sizeof(int);
    static int res[1 << 21];
    Convolution(a, n, b, m, res);
    for (int i = 0; i < n + m - 1; i++) cout << res[i] << " ";
    return 0;
}

上述代码中，`FFT`函数实现了FFT的核心算法，`Convolution`函数实现了两个多项式的卷积。其中，`Complex`结构体表示复数，`FFT`函数的flag参数为1表示进行DFT，为-1表示进行IDFT。`Convolution`函数中使用`static`关键字定义了A和B数组，避免在函数栈上分配大量空间导致栈溢出。注意这里的n和m分别表示两个多项式的次数（不是系数个数），res数组的长度应该为n+m-1。

需要注意的是，这里的数组实现与vector实现类似，只是使用数组代替了vector，因此在实际应用中，可以根据自己的需要选择vector或数组来实现FFT。