模板——快速傅里叶变换（递归）qq45739057的博客-

#include<cmath> #include<iostream> 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 < lim; i += 2) {   a0[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 < mid; i++) {   Complex t = w * a1[i];   a[i] = a0[i] + t;   a[i + mid] = a0[i] - t;   w = w * wn; } delete[]a0, a0 = NULL; delete[]a1, a1 = NULL; }  Complex F[N], G[N]; int main() { int n, m;  cin >> n >> m; for (int i = 0; i <= n; i++) cin >> F[i].R; for (int i = 0; i <= m; i++) cin >> 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; }