代码

#include<bits/stdc++.h>
#define ll long long
#define re register
#define INF 2147483647
using namespace std;

inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=x*10+s-48;
		s=getchar();
	}
	return f*x;
}

const int p=998244353,G=3;
const int N=1350000; 
inline int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%p)
		if(b&1) ans=1ll*ans*a%p;
	return ans;	
}

inline int add(int a,int b) 
{
	return a+b>=p?a+b-p:a+b;
}

inline int sub(int a,int b)
{
	return a-b<0?a-b+p:a-b;	
} 

const int invG=ksm(G,p-2);
int rev[N<<1],rev_len,n,m;
int f[N<<1],g[N<<1],ans[N<<1];

inline void getrev(int n)
{
	if(rev_len==n) return;
	rev_len=n;
	for(int i=0;i<n;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
}

void NTT(int *f,bool flag,int n)
{
	getrev(n);
	for(int i=0;i<n;i++)
		if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int len=2;len<=n;len<<=1)
	{
		int w=ksm((flag?G:invG),(p-1)/len);
		for(int k=0;k<n;k+=len)
		{
			int buf=1;
			for(int i=k;i<k+(len>>1);i++,buf=1ll*buf*w%p)
			{
				int tmp=1ll*buf*f[i+(len>>1)]%p;
				f[i+(len>>1)]=sub(f[i],tmp);
				f[i]=add(f[i],tmp);
			} 
		}
	}
	if(!flag)
	{
		int invn=ksm(n,p-2);
		for(int i=0;i<n;i++) f[i]=1ll*f[i]*invn%p;
	}
}

void times(int *f,int n,int *g,int m,int *ans)
{
	int len=1;
	for(;len<=n+m;len<<=1);
	NTT(f,1,len),NTT(g,1,len);
	for(int i=0;i<len;i++) ans[i]=1ll*f[i]*g[i]%p;
	NTT(ans,0,len); 
}

int main()
{
	n=read(),m=read();
	for(int i=0;i<=n;i++) f[i]=read();
	for(int i=0;i<=m;i++) g[i]=read();
	times(f,n,g,m,ans);
	for(int i=0;i<=n+m;i++) printf("%d ",ans[i]);
	return 0;
}

评测结果