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;
}