代码

// Author:A weak man named EricQian
#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define Maxn 4000005
#define mod 998244353
#define G 3
#define invG 332748118
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
typedef long long ll;
inline int rd()
{
	int x=0;
	char ch,t=0;
	while(!isdigit(ch = getchar())) t|=ch=='-';
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x=t?-x:x;
}
inline ll maxll(ll x,ll y){ return x>y?x:y; }
inline ll minll(ll x,ll y){ return x<y?x:y; }
inline ll absll(ll x){ return x>0ll?x:-x; }
inline ll gcd(ll x,ll y){ return (y==0)?x:gcd(y,x%y); }
int N,M,n,invn;
int tr[Maxn],a[Maxn],b[Maxn];
inline int ksm(int x,int y=mod-2)
{
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
	return ret;
}
inline void ntt(int *F,int opt)
{
	for(int i=0;i<n;i++) if(i<tr[i]) swap(F[i],F[tr[i]]);
	for(int p=2;p<=n;p<<=1)
	{
		int tG=ksm((opt==1)?G:invG,(mod-1)/p),len=p>>1;
		for(int i=0;i<n;i+=p)
		{
			int buf=1;
			for(int j=0;j<len;j++)
			{
				int tmp=1ll*F[i+j+len]*buf%mod;
				F[i+j+len]=F[i+j]-tmp;
				if(F[i+j+len]<0) F[i+j+len]+=mod;
				F[i+j]=F[i+j]+tmp;
				if(F[i+j]>=mod) F[i+j]-=mod;
				buf=1ll*buf*tG%mod;
			}
		}
	}
}
int main()
{
	//ios::sync_with_stdio(false); cin.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=rd(),M=rd();
	for(n=1;n<=N+M;n<<=1);
	for(int i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
	for(int i=0;i<=N;i++) a[i]=rd();
	for(int i=0;i<=M;i++) b[i]=rd();
	ntt(a,1),ntt(b,1);
	for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;
	ntt(a,-1),invn=ksm(n);
	for(int i=0;i<=N+M;i++) printf("%lld ",1ll*a[i]*invn%mod);
	printf("\n");
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

评测结果