FFT

好难

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const double pi = acos(-1);
int n, m, rev[4 * N];
struct comp{double x, y;comp(double xx = 0, double yy = 0){x = xx; y = yy;}comp(double zc, double i, double k){x = zc * cos(2 * pi * i / k);y = zc * sin(2 * pi * i / k);}
}a[4 * N], b[4 * N], c[4 * N];
comp operator + (comp a, comp b){return comp(a.x + b.x, a.y + b.y);}
comp operator * (comp a, comp b){return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}
comp operator - (comp a, comp b){return comp(a.x - b.x, a.y - b.y);}
void FFT(comp *a, int len, int type){int wei = 30 - __builtin_clz(len);for(int i = 0; i < len; i++){rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << wei); }for(int i = 0; i < len; i++){if(rev[i] < i) swap(a[i], a[rev[i]]);}for(int k = 1; k * 2 <= len; k *= 2){for(int j = 0; j < len; j += k * 2){for(int i = 0; i < k; i++){comp w = comp(1, type * i, k * 2);comp f1 = a[j + i], f2 = a[j + i + k];a[j + i] = f1 + w * f2;a[j + i + k] = f1 - w * f2;}}}if(type == -1){for(int i = 0; i < len; i++){a[i].x /= len;a[i].y /= len;}}
}
void dxstime(comp *a, int n, comp *b, int m, comp * c){int len = 1 << (1 + (int)log2(n + m - 1));FFT(a, len, 1);FFT(b, len, 1);for(int i = 0; i < len; i++) c[i] = a[i] * b[i];FFT(c, len, -1);
}
int main(){cin.tie(0)->sync_with_stdio(0);cout.tie(0)->sync_with_stdio(0);cin >> n >> m;for(int i = 0; i <= n; i++) cin >> a[i].x;for(int i = 0; i <= m; i++) cin >> b[i].x;dxstime(a, n, b, m, c);for(int i = 0; i <= n + m; i++) cout << int(c[i].x + 0.5) << " ";return 0;
}