代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=4e6+10;
const ll mod=998244353, G=3, Gi=332748118;
inline ll read(){
	ll x; scanf("%lld", &x);
	return x;
}
inline ll qpow(ll a,ll b){
    ll ans=1, base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}
ll n,m,limit=1,L,r[maxn],a[maxn],b[maxn];
void NTT(ll *A, ll type){
	for(ll i=0;i<limit;i++)
		if(i<r[i]) swap(A[i], A[r[i]]);
	for(ll mid=1;mid<limit;mid*=2){
		ll Wn = qpow( type==1 ? G : Gi, (mod-1)/(mid*2));
		for(ll j=0;j<limit;j+=mid*2){
			ll w = 1;
			for(ll k=0;k<mid;k++,w=(w*Wn)%mod){
				ll x=A[j+k], y=w*A[j+k+mid]%mod;
				A[j+k]=(x+y)%mod;
				A[j+k+mid]=(x-y+mod)%mod;
			}
		}
	}
}
int main(){
	n=read(), m=read();
	for(ll i=0;i<=n;i++) a[i]=(read()+mod)%mod;
	for(ll i=0;i<=m;i++) b[i]=(read()+mod)%mod;
	while(limit<=n+m) limit*=2, L++;
	for(ll i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
	NTT(a, 1); NTT(b, 1);
	for(ll i=0;i<limit;i++) a[i]=a[i]*b[i];
	NTT(a, -1);
	ll inv = qpow(limit, mod-2);
	for(ll i=0;i<=n+m;i++)
		printf("%lld ", (a[i]*inv)%mod);
	return 0;
}

评测结果