代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define UP(i, s, e) for(auto i=s; i!=e; ++i)
namespace m{ // } 
constexpr double pi = 3.1415926535897932;
struct CC{
	double real, imag;
	CC(double r=0, double i=0){ real = r, imag = i; }
	CC operator=(CC b){
		CC& a = *this;
		a.real = b.real, a.imag = b.imag;
		return a;
	}
	CC operator+(CC b){
		CC& a = *this;
		return CC(a.real+b.real, a.imag+b.imag);
	}
	CC operator-(CC b){
		CC& a = *this;
		return CC(a.real-b.real, a.imag-b.imag);
	}
	CC operator*(CC b){
		CC& a = *this;
		return CC(a.real*b.real-a.imag*b.imag, a.real*b.imag+a.imag*b.real);
	}
};
void change(CC *y, int len){
	std::vector<int> rev;
	rev.reserve(len);
	rev[0] = 0;
	UP(i, 1, len){
		rev[i] = rev[i>>1] >> 1;
		if(i&1) rev[i] |= len>>1;
	}
	UP(i, 0, len) if(i<rev[i]) std::swap(y[i], y[rev[i]]);
}
void fft(CC *y, int len, int on){
	change(y, len);
	for(int h=2; h<=len; h<<=1){
		CC wn(cos(2*pi/h), on*sin(2*pi/h));
		for(int j=0; j<len; j+=h){
			CC w(1);
			UP(k, j, j+h/2){
				CC u = y[k], v = w * y[k+h/2];
				y[k] = u+v, y[k+h/2] = u-v;
				w = w * wn;
			}
		}
	}
	if(on == -1) UP(i, 0, len){
		y[i].real /= len;
	}
}
CC ia[1<<21], ib[1<<21], ic[1<<21];
int in, im;
void work(){
	scanf("%d%d", &in, &im);
	UP(i, 0, in+1) scanf("%lf", &ia[i].real);
	UP(i, 0, im+1) scanf("%lf", &ib[i].real);
	int len = 1;
	while(len < in+im+1) len<<=1;
	fft(ia, len, 1);
	fft(ib, len, 1);
	UP(i, 0, len){
		ic[i] = ia[i] * ib[i];
	}
	fft(ic, len, -1);
	UP(i, 0, in+im+1){
		printf("%d ", (int)(ic[i].real+0.5));
	}
}
}
int main(){m::work(); return 0;}

评测结果