模板——快速傅里叶变换（递归）
#include
#include
using namespace std;
const int N = 1e6 + 10;
const double PI = acos(-1);
struct Complex
{
double R, I;
Complex() { R = 0, I = 0; }
Complex(double r, double i) :R(r), I(i) {}
};
Complex operator+(Complex a, Complex b) { return Complex(a.R + b.R, a.I + b.I); }
Complex operator-(Complex a, Complex b) { return Complex(a.R - b.R, a.I - b.I); }
Complex operator*(Complex a, Complex b) { return Complex(a.R * b.R - a.I * b.I, a.R * b.I + a.I * b.R); }
void FFT(Complex* a, int lim, int op) {
if (lim == 1) return;
Complex* a0 = new Complex[lim + 1];
Complex* a1 = new Complex[lim + 1];
for (int i = 0; i > 1] = a[i];
a1[i >> 1] = a[i + 1];
}
FFT(a0, lim >> 1, op);
FFT(a1, lim >> 1, op);
Complex wn = Complex(cos(2.0 * PI / lim), op * sin(2.0 * PI / lim));
Complex w = Complex(1, 0);
int mid = lim >> 1;
for (int i = 0; i > n >> m;
for (int i = 0; i > F[i].R;
for (int i = 0; i > G[i].R;
int k = 1;
while (k <= n + m) k <<= 1;
FFT(F, k, 1);
FFT(G, k, 1);
for (int i = 0; i <= k; i++) {
F[i] = F[i] * G[i];
}
FFT(F, k, -1);
for (int i = 0; i <= n + m; i++) {
cout << (int)(F[i].R / k + 0.5) << " ";
}
return 0;
}
作者：DoIdo~
