代码

#include<cstdio>
#include<complex>
#include<algorithm>
typedef std::complex<double> cd;
int read()
{
	int a=0;char c;
	while((c=getchar())<'0');
	while(c>='0')a=a*10+(c^48),c=getchar();
	return a;
}
const double pi=acos(-1);
class _FFT
{
private:
	int r[2097152],lim;
public:
	void init(const int l)
	{
		lim=1<<l;const int l_=l-1;
		for(int i=0;i<lim;i++)r[i]=r[i/2]/2|(i&1)<<l_;
	}
	void operator()(cd*a,const int type)
	{
		for(int i=0;i<lim;i++)if(r[i]>i)std::swap(a[i],a[r[i]]);
		for(int mid=1;mid<lim;mid<<=1)
		{
			cd omega1(cos(pi/mid),type*sin(pi/mid));
			const int step=mid*2;
			for(int j=0;j<lim;j+=step)
			{
				cd omega=1;
				for(int k=0;k<mid;k++,omega*=omega1)
				{
					cd x=a[j+k],y=omega*a[j+mid+k];
					a[j+k]=x+y,a[j+mid+k]=x-y;
				}
			}
		}
	}
}FFT;
cd a[2097152],b[2097152];
int main()
{
	int n=read(),m=read(),l=32-__builtin_clz(n+m),lim=1<<l;FFT.init(l);
	for(int i=0;i<=n;i++)a[i]=read();FFT(a,1);
	for(int i=0;i<=m;i++)b[i]=read();FFT(b,1);
	for(int i=0;i<lim;i++)a[i]*=b[i];FFT(a,-1);
	for(int i=0;i<=n+m;i++)printf("%d ",int(a[i].real()/lim+0.5));
}

评测结果