代码

#include<bits/stdc++.h>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } 
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); } 

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=(1<<21)+1,P=998244353;
const int g=3;

// Complex

int n,m;
int rev[N];
ll a[N],b[N];

ll qpow(ll x,ll k){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

void FFT(int n,ll *a,int f) {
	rep(i,0,n-1) if(rev[i]>i) swap(a[i],a[rev[i]]);
	for(reg int i=1;i<n;i<<=1) {
		ll w=qpow(f==1?g:(P+1)/3,(P-1)/(i*2)),tmp;
		for(reg int l=0;l<n;l+=i*2) {
			ll e=1;
			for(reg int j=l;j<l+i;++j,e=e*w%P) {
				tmp=a[j+i]*e%P;
				a[j+i]=(a[j]-tmp)%P;
				a[j]=(a[j]+tmp)%P;
			}
		}
	}
}




int main(){
	n=rd(),m=rd();
	rep(i,0,n) a[i]=rd();
	rep(i,0,m) b[i]=rd();
	int R=1,c=0;
	while(R<=n+m) R<<=1,c++;
	rep(i,1,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(c-1));
	FFT(R,a,1),FFT(R,b,1);
	rep(i,0,R) a[i]=a[i]*b[i]%P;
	FFT(R,a,-1);
	ll base=qpow(R,P-2);
	rep(i,0,n+m) printf("%lld ",(a[i]*base%P+P)%P);
}

评测结果