代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
inline void read(int &x)
{
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
	while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0',c=getchar();}
	x=s*w;
}
const int MAXN=270010,mod=998244353;
#define rg register int
inline int quick_pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
const int g=3,gi=quick_pow(g,mod-2);
int pos[MAXN],limit=1,len;
inline void NTT(int *A,int type)
{
	for(rg i=0;i<limit;i++)
		if(i<pos[i])swap(A[i],A[pos[i]]);
	for(rg mid=1;mid<limit;mid<<=1)
	{
		int wn=quick_pow(type?g:gi,(mod-1)/(mid<<1));
		for(rg j=0;j<limit;j+=(mid<<1))
		{
			int w=1;
			for(rg k=0;k<mid;k++,w=1ll*w*wn%mod)
			{
				int a=A[j+k],b=1ll*w*A[j+mid+k]%mod;
				A[j+k]=(a+b)%mod;
				A[j+mid+k]=(a-b)%mod;
			}
		}
	}
	if(type)return ;
	int inv=quick_pow(limit,mod-2);
	for(rg i=0;i<limit;i++)
		A[i]=1ll*A[i]*inv%mod;
}
int n,m;
int A[MAXN],B[MAXN];
int main()
{
	read(n),read(m);
	for(rg i=0;i<=n;i++)read(A[i]);
	for(rg i=0;i<=m;i++)read(B[i]);
	while(limit<=n+m)limit<<=1,len++;
	for(rg i=0;i<limit;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
	NTT(A,1),NTT(B,1);
	for(rg i=0;i<limit;i++)
		A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,0);
	for(rg i=0;i<=n+m;i++)
		printf("%d ",A[i]<0?A[i]+mod:A[i]);
}

评测结果