代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define getchar() (*sS++)
#define add(x,y) ((x)+(y)>=MOD ? (x)+(y)-MOD : (x)+(y))
#define minus(x,y) ((x)-(y)<0 ? (x)-(y)+MOD : (x)-(y))
typedef unsigned int uint;
typedef std::vector<int> vi;
typedef std::vector<int> Poly;
const int G=3;
const int maxn=1<<18|7;
const int MOD=998244353;
char s[1<<20];
char *sS=s;
inline void I(int &x){
	register int ch;
	while(ch=getchar(),ch<'/');x=ch-'0';
	while(ch=getchar(),ch>'/')x=((x+(x<<2))<<1)+ch-'0';
}
inline void O(int x){
	if(x>9)O(x/10),putchar('0'+x%10);
	else putchar('0'+x);
}
inline int Pow(int x,int k){
	int ans=1;
	for(;k;x=x*1ll*x%MOD,k>>=1)
		if(k&1)ans=ans*1ll*x%MOD;
	return ans;
}
inline vi Getrev(int n){
	int len=1,cnt=0;
	while(len<n)len<<=1,++cnt;
	vi rev(len);
	for(int i=1;i<len;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));
	return rev;
}
inline void NTT(Poly &A,vi &rev,int K){
	register int i,j,k,t,wn;
	int len=rev.size();A.resize(len);
	for(i=0;i<len;++i) if(i<rev[i])
		std::swap(A[i],A[rev[i]]);
	vi w(len);w[0]=1;
	for(i=1,t=2;i<len;i<<=1,t<<=1){
		wn=Pow(G,(K*(MOD-1)/t+MOD-1)%(MOD-1));
		for(k=i-2;k>=0;k-=2)
			w[k+1]=wn*1ll*(w[k]=w[k>>1])%MOD;
		for(j=0;j<len;j+=t) for(k=0;k<i;++k){
			int x=A[j+k],y=A[j+k+i]*1ll*w[k]%MOD;
			A[j+k]=add(x,y),A[j+k+i]=minus(x,y);
		}
	}
	if(K==-1){
		t=Pow(len,MOD-2);
		for(i=0;i<len;++i)
			A[i]=A[i]*1ll*t%MOD;
	}
}
inline void operator *(Poly &A,Poly &B){
	int n=A.size()+B.size()-1;
	vi rev(Getrev(n));
	NTT(A,rev,1),NTT(B,rev,1);
	for(uint i=0;i<A.size();++i)
		A[i]=A[i]*1ll*B[i]%MOD;
	NTT(A,rev,-1);
	for(int i=0;i<n;++i)
		O(A[i]),putchar(' ');
	putchar('\n');
}
int n,m;
Poly A,B;
int main(){
	fread(s,1,1<<20,stdin);
	I(n),I(m);
	A.resize(n+1),B.resize(m+1);
	for(int i=0;i<=n;++i)I(A[i]);
	for(int i=0;i<=m;++i)I(B[i]);
	return A*B,0;
}

评测结果