代码

#include <bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
namespace NTT {
	const int N=270000,P=998244353;
	int n,A[N],B[N],R[N],W[N];
	int Pow (int x,int k) {
		int r=1;
		while (k) {
			if (k&1) r=1LL*r*x%P;
			x=1LL*x*x%P; k>>=1;
		}
		return r;
	}
	void DFT (int *A,int o) {
		For(i,0,n-1) if (i<R[i]) swap(A[i],A[R[i]]);
		for(int i=1;i<n;i<<=1) {
			for(int j=0;j<n;j+=i+i) {
				For(k,0,i-1) {
					int t=1LL*W[n/i*k]*A[j+k+i]%P;
					A[j+k+i]=(A[j+k]-t+P)%P;
					A[j+k]=(A[j+k]+t)%P;
				}
			}
		}
		if (o) {
			int x=Pow(n,P-2);
			For(i,0,n-1) A[i]=1LL*A[i]*x%P;
		}
	}
	void Mul (int *_A,int a,int *_B,int b) {
		For(i,0,a-1) A[i]=_A[i];
		For(i,0,b-1) B[i]=_B[i];
		for(n=1;n<a+b;n<<=1);
		For(i,0,n-1) R[i]=(R[i>>1]>>1)|((i&1)*(n/2));
		W[0]=1,W[1]=Pow(3,(P-1)/n>>1);
		For(i,2,n-1) W[i]=1LL*W[i-1]*W[1]%P;
		DFT(A,0),DFT(B,0);
		For(i,0,n-1) _A[i]=1LL*A[i]*B[i]%P;
		W[1]=Pow(W[1],P-2);
		For(i,2,n-1) W[i]=1LL*W[i-1]*W[1]%P;
		DFT(_A,1);
	}
}
using NTT::Mul;

const int N=270000;
int A[N],B[N],a,b;
int main () {
	scanf("%d%d",&a,&b),++a,++b;
	For(i,0,a-1) scanf("%d",&A[i]);
	For(i,0,b-1) scanf("%d",&B[i]);
	Mul(A,a,B,b);
	For(i,0,a+b-2) printf("%d ",A[i]);
	return 0;
}

评测结果