代码

#include <bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
namespace FFT {
	const int N=270000;
	const double pi=acos(-1);
	struct cp {
		double x,y;
		cp operator + (const cp &_) {return (cp){x+_.x,y+_.y};}
		cp operator - (const cp &_) {return (cp){x-_.x,y-_.y};}
		cp operator * (const cp &_) {return (cp){x*_.x-y*_.y,x*_.y+y*_.x};}
	}A[N],B[N],W[N],y;
	int R[N];
	void DFT(cp *a,int n,int p){
	    For(i,0,n-1) if(i<R[i]) swap(a[i],a[R[i]]);
	    W[0]=(cp){1,0};
	    for(int i=1;i<n;i<<=1){
	        cp wn={cos(pi/i),p*sin(pi/i)};
	        for(int j=i-2;j>=0;j-=2) W[j+1]=wn*(W[j]=W[j>>1]);
	        for(int j=0;j<n;j+=i<<1){
	            For(k,0,i-1){
	                cp x=W[k]*a[i+j+k];
	                a[j+k+i]=a[j+k]-x;
	                a[j+k]=a[j+k]+x;
	            }
	        }
	    }
	}
	void Mul (int *_A,int a,int *_B,int b) {
		int n=(1<<(int)log2(a+b)<<1);
		For(i,0,n-1) R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
		For(i,0,a-1) A[i].x=_A[i];
		For(i,0,b-1) B[i].x=_B[i];
		cp t=(cp){cos(2*pi/n),sin(2*pi/n)};
		W[0]=(cp){1,0}; For(i,1,n-1) W[i]=W[i-1]*t;
		DFT(A,n,1),DFT(B,n,1);
		t=(cp){cos(2*pi/n),-sin(2*pi/n)};
		W[0]=(cp){1,0}; For(i,1,n-1) W[i]=W[i-1]*t;
		For(i,0,n-1) A[i]=A[i]*B[i];
		DFT(A,n,-1);
		For(i,0,n-1) _A[i]=A[i].x/n+0.5;
	}
}
using FFT::Mul;

const int N=100007;
int A[N],B[N],a,b;
int main () {
	scanf("%d%d",&a,&b),++a,++b;
	For(i,0,a-1) scanf("%d",&A[i]);
	For(i,0,b-1) scanf("%d",&B[i]);
	Mul(A,a,B,b);
	For(i,0,a+b-2) printf("%d ",A[i]);
	return 0;
}

评测结果