代码

#include<cstdio>
#include<cstring>
#define mod 998244353
typedef long long LL;
typedef unsigned long long ULL;
int W[2][262144],_i[19];
inline int fmo(int a,int b)
{
	ULL x = (ULL)a*b;
	ULL lo = x&0xFFFFFFFF,hi = x>>32;
	lo *= 2309898375ULL, hi *= 2309898375ULL;
	hi += lo>>32;
	int r = x-(hi>>29)*998244353;
	if(r >= 998244353)r -= 998244353;
	return r;
}
inline int ksm(LL a,LL b){int r=1;for(;b;a=fmo(a,a),b>>=1)if(b&1)r=fmo(r,a);return r;}
void NTT_Init()
{
	int i,j,t,*x;
	for(i=1;i<262144;i<<=1)
	{
		W[0][i] = 1, t = ksm(3,(mod-1)/i/2);
		for(j=1;j<i;j++)W[0][i+j] = fmo(W[0][i+j-1],t);
		W[1][i] = 1, t = ksm(332748118,(mod-1)/i/2);
		for(j=1;j<i;j++)W[1][i+j] = fmo(W[1][i+j-1],t);
	}
	for(_i[0]=i=1;i<19;i++)_i[i] = fmo(_i[i-1],499122177);
}
void NTT(int *f,int len,int sign)
{
	int i,j,k,*w,*p,*q,t;sign=sign==-1;
	for(i=j=0;i<len;i++){if(i<j)f[i]^=f[j]^=f[i]^=f[j];for(k=len>>1;(j^=k)<k;k>>=1);}
	for(i=1;i<len;i<<=1)for(j=0;j<len;j+=i<<1)for(w=W[sign]+i,q=(p=f+j)+i,k=0;k<i;k++)
		{t=fmo(*q,*w++);if((*q=*p-t)<0){*q+=mod;}if((*p+=t)>=mod){*p-=mod;}p++,q++;}
	if(sign)for(k=_i[__builtin_ctz(len)],i=0;i<len;i++)f[i] = fmo(k,f[i]);
}
int a[262144],b[262144];
int main()
{
	int n,m,i,l;
	NTT_Init();
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;i++)scanf("%d",a+i);
	for(i=0;i<=m;i++)scanf("%d",b+i);
	n = n+m+1;
	for(l=1;l<n;l<<=1);
	NTT(a,l,1), NTT(b,l,1);
	for(i=0;i<l;i++)a[i] = fmo(a[i],b[i]);
	NTT(a,l,-1);
	for(i=0;i<n;i++)printf("%d ",a[i]);
	return 0;
}

评测结果