代码

#include<bits/stdc++.h>
using namespace std;
typedef long long lxl;
const int Gr=3,base=21;
const int MOD=998244353;

template<typename Type=int> inline Type read(){
	Type x=0,f=1;char ch=getchar();
	while(!isdigit(ch))(ch=='-')&&(f=-f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
template<typename Type> inline bool chkmin(Type &a,Type b){return (b<a)?(a=b,1):0;}
template<typename Type> inline bool chkmax(Type &a,Type b){return (a<b)?(a=b,1):0;}
inline int expow(int n,int k){
	int ans=1;
	for(;k;k>>=1,n=1ll*n*n%MOD)(k&1)&&(ans=1ll*ans*n%MOD);
	return ans;
}

int w[1<<base];
inline void init(){
	for(int len=1;len<(1<<base);len<<=1){
		const int tmp=expow(Gr,MOD/(len<<1));w[len]=1;
		for(int i=1;i<len;++i) w[i|len]=1ll*w[(i-1)|len]*tmp%MOD;
	}
}
inline void DFT(int *a,int n){
	int i,j,len;
	static lxl T[1<<base];
	for(i=0;i<n;++i) T[i]=a[i];
	for(len=n>>1;len;len>>=1){
		if(len==(n>>15)) for(i=0;i<n;++i) T[i]%=MOD;
		for(i=0;i<n;i+=(len<<1))
			for(j=0;j<len;++j){
				const int tmp=T[i|j|len]%MOD;
				T[i|j|len]=1ull*(T[i|j]+MOD-tmp)*w[j|len]%MOD;
				T[i|j]+=tmp;
			}
	}
	for(i=0;i<n;++i) a[i]=T[i]%MOD;
}
inline void IDFT(int *a,int n){
	int i,j,len;
	static lxl T[1<<base];
	for(i=0;i<n;++i) T[i]=a[i];
	for(len=1;len<n;len<<=1){
		if(len==(1<<15)) for(i=0;i<n;++i) T[i]%=MOD;
		for(i=0;i<n;i+=(len<<1))
			for(j=0;j<len;++j){
				const int tmp=1ull*T[i|j|len]*w[j|len]%MOD;
				T[i|j|len]=T[i|j]+MOD-tmp;T[i|j]+=tmp;
			}
	}
	const int tmp=MOD-MOD/n;
	for(i=0;i<n;++i) a[i]=1ull*T[i]*tmp%MOD;
	reverse(a+1,a+n);
}

int n,f[1<<base];
int m,g[1<<base];

int main(){
//	freopen("P3803_4.in","r",stdin);
//	freopen("test.out","w",stdout);
	int i,lim;init();
	n=read()+1;m=read()+1;
	for(i=0;i<n;++i) f[i]=read();
	for(i=0;i<m;++i) g[i]=read();
	for(lim=1;lim<(n+m-1);lim<<=1);
	DFT(f,lim);DFT(g,lim);
	for(i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%MOD;
	IDFT(f,lim);
	for(i=0;i<n+m-1;++i) printf("%d ",f[i]);
	return 0;
}

评测结果