代码

#include<bits/stdc++.h>
namespace imzzy{
	#define endl '\n'
	#define rgi register int
	#define ll long long
	#define rgl register long long
	class fastin{private:int _ch,_f;
	public:inline fastin&operator>>(char&c){c=getchar();return*this;}
	template<typename _Tp>inline fastin&operator>>(_Tp&_x){
	_x=0;while(!isdigit(_ch))_f|=(_ch==45),_ch=getchar();
	while(isdigit(_ch))_x=(_x<<1)+(_x<<3)+(_ch^48),_ch=getchar();
	_f&&(_x=-_x,_f=0);return*this;}fastin(){_ch=_f=0;}
	}fin;class fastout{private:int _num[32],_head;
	public:inline fastout&operator<<(char c){putchar(c);return*this;}
	template<typename _Tp> inline fastout&operator<<(_Tp _x){
	_Tp _k;if(_x==0){putchar('0');return *this;}if(_x<0)putchar('-'),_x=-_x;
	while(_x>0)_k=_x/10,++_head,_num[_head]=(_x-(_k<<1)-(_k<<3))^48,_x=_k;
	while(_head>0)putchar(_num[_head]),--_head;return*this;}fastout(){_head=0;}
	}fout;inline void P_INIT(){
	#ifdef D_STDOUT_UNBUFFERED
	setbuf(stdin,NULL),setbuf(stdout,NULL);
	#endif
}}using namespace imzzy;
// ----------------------------
// #define int ll
// using namespace std;
const double pi=acos(-1.0);
const int mod=998244353,inf=1201201201;
const int maxn=1000004;


struct complex {
	double x,y;
	complex(double a=0,double b=0) {x=a,y=b;}
	inline complex operator+(const complex&a) const {return complex(x+a.x,y+a.y);}
	inline complex operator-(const complex&a) const {return complex(x-a.x,y-a.y);}
	inline complex operator*(const complex&a) const {return complex(x*a.x-y*a.y,x*a.y+y*a.x);}
};
void fft(int lim,std::vector<complex>&a,int type) {
	if(lim==1) return;
	std::vector<complex> a1,a2;
	for(rgi i=0;i<lim;i+=2) a1.push_back(a[i]),a2.push_back(a[i+1]);
	fft(lim>>1,a1,type),fft(lim>>1,a2,type);
	complex Wn=complex(cos(2*pi/lim),type*sin(2*pi/lim)),w=complex(1,0);
	for(rgi i=0;i<lim>>1;++i,w=w*Wn) a[i]=a1[i]+w*a2[i],a[i+(lim>>1)]=a1[i]-w*a2[i];
}
inline std::vector<int> mul(const std::vector<int> &x,const std::vector<int> &y) {
	std::vector<complex> a,b; std::vector<int> res;
	int n=x.size()-1,m=y.size()-1,lim=1; while(lim<=n+m) lim<<=1;
	for(rgi i=0;i<lim;++i) if(i<=n) a.push_back(complex(x[i],0)); else a.push_back(complex(0,0));
	for(rgi i=0;i<lim;++i) if(i<=m) b.push_back(complex(y[i],0)); else b.push_back(complex(0,0));
	fft(lim,a,1),fft(lim,b,1);
	for(rgi i=0;i<lim;++i) a[i]=a[i]*b[i];
	fft(lim,a,-1);
	for(rgi i=0;i<=n+m;++i) res.push_back((int)(a[i].x/lim+0.5));
	return res;
}

signed main()
{P_INIT();
	int n,m,x; fin>>n>>m;
	std::vector<int> a,b,c;
	for(rgi i=0;i<=n;++i) fin>>x,a.push_back(x);
	for(rgi i=0;i<=m;++i) fin>>x,b.push_back(x);
	c=mul(a,b);
	for(rgi i=0;i<=n+m;++i) fout<<c[i]<<' ';
	return 0;
}
// ----------------------------
// by imzzy

评测结果