代码

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=(1<<18|5);
const int P=998244353;
const double PI=acos(-1);

struct Complex
{
	double re,im;
	Complex operator +(const Complex &_)const{return (Complex){re+_.re,im+_.im};}
	Complex operator -(const Complex &_)const{return (Complex){re-_.re,im-_.im};}
	Complex operator *(const Complex &_)const{return (Complex){re*_.re-im*_.im,re*_.im+im*_.re};}
	Complex operator /(const int &_)const{return (Complex){re/_,im/_};}
};
namespace _Polynomial
{
	Complex S[N],T[N],U[N],V[N];
	static const int K=(1<<15)-1,L=15;
	void DFT(Complex *a,int op,int n)
	{
		static int rev[N],pre=0;
		static Complex w[N];
		if(n!=pre)
		{
			FOR(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
			FOR(i,0,n-1)w[i]=(Complex){cos(2*PI*i/n),sin(2*PI*i/n)};
			pre=n;
		}
		FOR(i,0,n-1)if(i<rev[i])std::swap(a[i],a[rev[i]]);
		for(register int i=2;i<=n;i<<=1)
			for(register int j=0;j<n;j+=i)
			{
				Complex *p=&a[j],*q=&a[j+i/2];
				for(register int k=0;k<i/2;++k)
				{
					Complex u=p[k],t=w[op==1?n/i*k:(n-n/i*k)&(n-1)]*q[k];
					p[k]=u+t;
					q[k]=u-t;
				}
			}
		if(op==-1)FOR(i,0,n-1)a[i]=a[i]/n;
	}
	void multiply(int *A,int n_A,int *B,int n_B,int *C)
	{
		Complex *D=S,*E=T,*F=U,*G=V;
		int n=1;
		while(n<n_A+n_B-1)n<<=1;
		FOR(i,0,n_A-1)D[i].re=A[i]&K,D[i].im=A[i]>>L;
		FOR(i,n_A,n-1)D[i].re=D[i].im=0;
		FOR(i,0,n_B-1)E[i].re=B[i]&K,E[i].im=B[i]>>L;
		FOR(i,n_B,n-1)E[i].re=E[i].im=0;

		DFT(D,1,n),DFT(E,1,n);
		FOR(i,0,n-1)
		{
			int j=(n-i)&(n-1);
			F[i]=(Complex){(D[i].re+D[j].re)/2,(D[i].im-D[j].im)/2}*E[i];
			G[i]=(Complex){(D[i].im+D[j].im)/2,(D[j].re-D[i].re)/2}*E[i];
		}
		DFT(F,-1,n),DFT(G,-1,n);
		FOR(i,0,n_A+n_B-2)
		{
			ll t1=F[i].re+0.5,t2=F[i].im+0.5,t3=G[i].re+0.5,t4=G[i].im+0.5;
			C[i]=(t1+((t2+t3)%P<<L)+((t4%P<<L)%P<<L))%P;
		}
	}
};
int A[N],B[N],n,m;

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		n++,m++;
		FOR(i,0,n-1)scanf("%d",&A[i]);
		FOR(i,0,m-1)scanf("%d",&B[i]);
		_Polynomial::multiply(A,n,B,m,A);
		FOR(i,0,n+m-2)printf("%d%c",A[i],(i==n+m-2?'\n':' '));
	}
	return 0;
}

评测结果