模板——快速傅里叶变换（迭代版本）
讲解
个人理解
作者：DoIdo~
#include
#include
#include
using namespace std;
const double PI = acos(-1);
const int N = 1e6 + 10;
//复数结构体
struct Complex {
double R, I;
Complex() { R = 0.0, I = 0.0; }
Complex(double r, double i) :R(r), I(i) {}
};
Complex F[N], G[N];
//重载操作符
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); }
int rev[N], len, lim = 1;
void FFT(Complex* a, int opt) {
for (int i = 0; i < lim; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int dep = 1; dep <= log2(lim); dep++) {
int m = 1 << dep;
Complex wn = Complex(cos(2.0 * PI / m), opt * sin(2.0 * PI / m));
for (int k = 0; k < lim; k += m) {
Complex w = Complex(1, 0);
for (int j = 0; j < m / 2; j++) {
Complex t = w * a[k + j + m / 2];
Complex u = a[k + j];
a[k + j] = u + t;
a[k + j + m / 2] = u - t;
w = w * wn;
}
}
}
if (opt == -1) for (int i = 0; i > n >> m;
for (int i = 0; i > F[i].R;
for (int i = 0; i > G[i].R;
while (lim < n + m + 2) lim <<= 1, len++;
for (int i = 1; i > 1] >> 1) | ((i & 1) << (len - 1));
}
FFT(F, 1), FFT(G, 1);
for (int i = 0; i <= lim; i++) {
F[i] = F[i] * G[i];
}
FFT(F, -1);
for (int i = 0; i <= n + m; i++) {
cout << (int)(F[i].R + 0.5) << " ";
}
return 0;
}
作者：DoIdo~
