代码

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef pair<int,int> PII;
int plen,ptop,pstk[40];
char rdc[1<<20],out[1<<20],*rS,*rT;
#define gc() (rS==rT?rT=(rS=rdc)+fread(rdc,1,1<<20,stdin),(rS==rT?EOF:*rS++):*rS++)
#define pc(x) out[plen++]=(x)
#define flush() fwrite(out,1,plen,stdout),plen=0
template<class T=int>inline T read(){
    T x=0;char ch;bool f=1;
    while(!isdigit(ch=gc()))if(ch=='-')f^=1;
    do x=(x<<1)+(x<<3)+(ch^48);while(isdigit(ch=gc()));
    return f?x:-x;
}
inline int read(char*const s){
	char *t=s,ch;
    while(!isgraph(ch=gc()));
	do(*(t++))=ch;while(isgraph(ch=gc()));
	return (*t)='\000',t-s;
}
template<class T=int>inline void write(T x){
	if(plen>=1000000)flush();
	if(!x)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	for(;x;x/=10)pstk[++ptop]=x%10;
	while(ptop)pc(pstk[ptop--]+'0');
}
inline void write(const char*s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
inline void write(char*const s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
typedef pair<int,int> PII;
typedef vector<int> poly;
const int Mod=998244353,G=3,Lim=64,winv=932051910;
const LL Mod2=996491788296388609LL;
poly w0={1},W0;
inline int fadd(int x,int y){
	x+=y-2*Mod;
	return x>=0?x:x+2*Mod;
}
inline int fsub(int x,int y){
	x-=y;
	return x>=0?x:x+2*Mod;
}
inline int reduce(LL x){
	uint t=(uint)x*(Mod-2);
	return (x+(LL)t*Mod)>>32;
}
inline int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=(LL)x*x%Mod)
		if(y&1)res=(LL)res*x%Mod;
	return res;
}
template<int tn>
inline void dft(poly &P){
	int m=P.size(),n=m/tn,L=w0.size();
	if(L*2<n)for(w0.resize(n/2);L*2<n;L<<=1){
		int cr=qpow(G,Mod/(L<<2));
		for(int i=0;i<L;++i)w0[i+L]=(LL)cr*w0[i]%Mod;
	}
	if(W0.size()<w0.size()){
		int pr=W0.size(),ed=w0.size();
		W0.resize(ed);
		for(int i=pr;i<ed;++i)W0[i]=reduce((LL)winv*w0[i]);
	}
	for(int k=n,st1,st2;st1=k*tn,st2=st1>>1,k>1;k>>=1)
		for(int i=0,ie=n/k;i<ie;++i)
			for(int p=i*st1,pe=p+st2;p<pe;++p){
				int q=p+st2,z=reduce((LL)P[q]*W0[i]);
				P[q]=fsub(P[p],z),P[p]=fadd(P[p],z);
			}
    for(int &i:P)(i>=Mod)?(i-=Mod):0;
}
template<int tn>
inline void idft(poly &P){
	int m=P.size(),n=m/tn,ni=qpow(n,Mod-2);
	poly rev(n);
	for(int i=1;i<n;++i)rev[i]=rev[i/2]/2+(i&1)*(n/2);
	for(int &i:P)i=1LL*i*ni%Mod;
	for(int i=1;i<n;++i)if(i<rev[i])
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*rev[i]);
	for(int i=1;i<n/2;++i)
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*(n-i));
	dft<tn>(P);
	for(int i=1;i<n;++i)if(i<rev[i])
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*rev[i]);
}
template<int tn>
inline void mul_mod(poly &P,poly &Q){
	int m=P.size(),n=m/tn;
	dft<tn>(P),dft<tn>(Q);
	for(int i=0;i<n;++i){
		vector<uLL>ans(tn<<1);
		for(int j=0;j<tn;++j){
			for(int k=0;k<tn;++k)
				ans[j+k]+=(LL)P[i*tn+j]*Q[i*tn+k];
			if(!((~j)&7))for(int k=j;k<j+tn;++k)
				if(ans[k]>=(Mod2<<3))ans[k]-=Mod2<<3;
		}
		int c=((i&1)?Mod-w0[i>>1]:w0[i>>1]);
		for(int j=0;j<tn;++j)
			P[i*tn+j]=(ans[j]+ans[j+tn]%Mod*c)%Mod;
	}
	idft<tn>(P);
}
template<size_t... m>
inline void solve(index_sequence<m...>,int n,poly &P,poly &Q){
	static void (*ptrs[])(poly&,poly&)={&mul_mod<m+1>...};
	ptrs[n-1](P,Q);
}
inline poly mul(poly P,poly Q){
	int pn=P.size(),qn=Q.size(),rn=pn+qn-1,b=1;
	while((Lim<<b)<rn)++b;
	int tn=((rn-1)>>b)+1,m=tn<<b;
	P.resize(m),Q.resize(m);
	solve(make_index_sequence<Lim>{},tn,P,Q);
	return P.resize(rn),P;
}
signed main(){
	int n=read()+1,m=read()+1;
	poly P(n),Q(m);
	for(int &i:P)i=read();
	for(int &i:Q)i=read();
	poly R=mul(P,Q);
	for(int &i:R)write(i),pc(' ');
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
	return flush(),0;
}
/*
*/

评测结果