代码

#include<set>
#include<map>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

const int N=4194310,P=998244353;

struct IO_tp
{
	static const int Sbuf=1<<21;
	char buf[Sbuf], *S, *T, c; int f;
	#define gc() (S==T?(T=(S=buf)+fread(buf,1,sizeof(buf),stdin),(S==T?EOF:*S++)):*S++)
	template<class I>
	inline IO_tp& operator >> (I &x)
	{
		for(f=1, c=gc(); c<'0'||c>'9'; c=gc()) if(c=='-') f=-1;
		for(x=0; c>='0'&&c<='9'; c=gc()) x=x*10+(c^48); x*=f;
		return *this;
	}
}io;

int fpow(int a,int b)
{
	ll w(1),o(a);
	while(b)
	{
		if(b&1)w=w*o%P;
		o=o*o%P;
		b>>=1;
	}
	return w;
}

const int G=19260817,iG=fpow(G,P-2);

int n,m,A[N],B[N],L,U,h[N];

void NTT(int*f,int T)
{
	int w,wn,x,y;
	for(int i=0; i<U; i++)
		if(i<h[i])
			swap(f[i],f[h[i]]);
	for(int l=1; l<U; l<<=1)
	{
		wn=fpow(T>0?G:iG,(P-1)/(l<<1));
		for(int i=0; i<U; i+=l<<1)
		{
			w=1;
			for(int j=i; j<i+l; j++)
			{
				x=f[j];
				y=(ll)f[j+l]*w%P;
				f[j]=(x+y)%P;
				f[j+l]=(x+P-y)%P;
				w=(ll)w*wn%P;
			}
		}
	}
	if(T<0)
	{
		w=fpow(U,P-2);
		for(int i=0; i<U; i++)
			f[i]=(ll)f[i]*w%P;
	}
}

int main()
{
	io>>n>>m;
	for(int i=0; i<=n; i++)io>>A[i];
	for(int i=0; i<=m; i++)io>>B[i];
	for(U=1; U<=n+m; U<<=1)L++;
	for(int i=0; i<U; i++)
		h[i]=(h[i>>1]>>1)|((i&1)<<(L-1));
	NTT(A, 1);
	NTT(B, 1);
	for(int i=0; i<U; i++)
		A[i]=(ll)A[i]*B[i]%P;
	NTT(A,-1);
	for(int i=0; i<=n+m; i++)
		printf("%d ",A[i]);
	return 0;
}

评测结果