代码

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int read(){
	int n=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+(c^48), c=getchar();
	return n;
}

const int Mx=3e5;
const double Pi=acos(-1);
struct Complex{
	double Real,Ima;
	Complex operator + (const Complex& a) const { return (Complex){Real+a.Real,Ima+a.Ima};}
	Complex operator - (const Complex& a) const { return (Complex){Real-a.Real,Ima-a.Ima};}
	Complex operator * (const Complex& a) const { return (Complex){Real*a.Real-Ima*a.Ima,Real*a.Ima+Ima*a.Real};}
	Complex operator += (const Complex& a) { return (*this)=(Complex){Real+a.Real,Ima+a.Ima};}
	Complex operator -= (const Complex& a) { return (*this)=(Complex){Real-a.Real,Ima-a.Ima};}
	Complex operator *= (const Complex& a) { return (*this)=(Complex){Real*a.Real-Ima*a.Ima,Real*a.Ima+Ima*a.Real};}
}F[Mx];
int Rfl[Mx];
void FFT(Complex A[],int Len,int Type){
	for(int i=0;i<Len;++i) if(i<Rfl[i]) swap(F[i],F[Rfl[i]]);
	for(int i=1;i<Len;i<<=1){
		Complex Omiga={cos(Pi/i),sin(Pi/i)*Type};
		for(int j=0;j<Len;j+=(i<<1)){
			Complex Unit={1.0,0.0};
			for(int k=0;k<i;++k, Unit*=Omiga){
				Complex A1=A[k+j],A2=A[k+j+i]*Unit;
				A[k+j]=A1+A2, A[k+j+i]=A1-A2;
			}
		}
	}
}
int main(){
	int n=read(),m=read();
	for(int i=0;i<=n;++i) F[i].Real=read();
	for(int i=0;i<=m;++i) F[i].Ima=read();
	int Len=1,pw=0;
	while(Len<=n+m) Len<<=1, ++pw;
	for(int i=1;i<Len;++i) Rfl[i]=(i&1)?(Rfl[i-1]+(1<<(pw-1))):Rfl[i>>1]>>1;
	FFT(F,Len,1);
	for(int i=0;i<Len;++i) F[i]*=F[i];
	FFT(F,Len,-1);
	for(int i=0;i<=n+m;++i) printf("%d ",(int)(0.5+F[i].Ima/(Len<<1)));
	return 0;
}

评测结果