代码

#include<bits/stdc++.h>
namespace iobuff{
	const int len=1<<20;
	#ifdef DEBUG
		#define gc() getchar();
	#else
		char ibuf[len+5],*st=ibuf,*ed=ibuf;
		#define gc() (st==ed&&(ed=(st=ibuf)+fread(ibuf,1,len,stdin),st==ed)?EOF:*st++)
	#endif
	inline char gchar(){return gc();}
	template<typename T=int>
	inline T gint(T x=0){
		bool f=0;char c=gc();for(;c>'9'||c<'0';c=gc())f=c=='-';
		for(x=c-48,c=gc();c<='9'&&c>='0';c=gc())x=x*10+c-48;
		return f?-x:x;
	}
	#undef gc
	#ifdef DEBUG
		#define pc(x) putchar(x)
	#else
		char obuf[len+5],*p=obuf;
		#define pc(x) (p==obuf+len&&(fwrite(obuf,1,p-obuf,stdout),p=obuf),*p++=x)
		struct autoflush{~autoflush(){fwrite(obuf,1,p-obuf,stdout),p=obuf;}}autoflusher;
	#endif
	inline char pchar(char x){return pc(x),x;}
	template<typename T=int>
	inline void pint(T x){
		static char s[128];char *t=s;
		x<0&&(pc('-'),x=-x);
		do *t++='0'+x%10; while(x/=10);
		while(t!=s)pc(*--t);
	}
	#undef pc
}
using namespace std;
using iobuff::gint;
using iobuff::pint;
using namespace std;
const int mod=998244353,gen=3;
typedef long long i64;
typedef unsigned long long u64;
namespace math{
	// fast power , (x and ans) must in [-mod,mod], y must in [-mod+1,mod-1] 
	template<typename T=int>
	inline T fsp(i64 x,int y,i64 ans=1){
		for(y<0?y+=mod-1:0;y;y>>=1,x=x*x%mod)
			y&1?ans=ans*x%mod:0;
		return ans;
	}
	namespace fast_number_theory_transform{
		const int maxbit=22;
		i64 mod_root[maxbit+1]; // mod_root[i]**(2**i) == 1
		i64 mod_iroot[maxbit+1]; // mod_iroot[i]*mod_root[i] == 1

		__attribute__((constructor))
		inline void init_mod_root(){
			mod_root[maxbit]=fsp(gen,mod>>(maxbit+1));
			mod_iroot[maxbit]=fsp(mod_root[maxbit],mod-2);
			for(int i=maxbit;i-->0;)
				mod_root[i]=mod_root[i+1]*mod_root[i+1]%mod,
				mod_iroot[i]=mod_iroot[i+1]*mod_iroot[i+1]%mod;
		}

		// butterfly transform
		// int rev[1<<24];
		template<class T>
		inline void butterfly(T* p,int bit) {
			for(unsigned i=0,j=0;i<(1u<<bit);i++){
				// j=rev[i]=(rev[i>>1]>>1)^((i&1)<<(bit-1));
				if(i>j)swap(p[i],p[j]);
				for(unsigned l=1u<<(bit-1);(j^=l)<l;l>>=1);
			}
		}
		
		inline void ntt(int* a,int *b,int bit,bool f=0){
			int lim=1<<bit;
			for(int k=bit;k-->0;){
				i64 pw=1;
				for(int j=0;j<(1<<k)-1;j++,pw=pw*mod_root[k]%mod){
					for(int i=j;i<lim;i+=1<<(k+1)){
						int x=a[i],y=a[i^(1<<k)];
						(a[i]+=y)<mod?0:a[i]-=mod;
						a[i^(1<<k)]=pw*(x+mod-y)%mod;
						x=b[i],y=b[i^(1<<k)];
						(b[i]+=y)<mod?0:b[i]-=mod;
						b[i^(1<<k)]=pw*(x+mod-y)%mod;
					}
				}
				for(int i=(1<<k)-1;i<lim;i+=1<<(k+1)){
					int x=a[i],y=a[i^(1<<k)];
					(a[i]+=y)<mod?0:a[i]-=mod;
					a[i^(1<<k)]=pw*(x+mod-y)%mod;
					x=b[i],y=b[i^(1<<k)];
					(b[i]+=y)<mod?0:b[i]-=mod;
					b[i^(1<<k)]=pw*(x+mod-y)%mod;
				}
			}if(f)butterfly(a,bit),butterfly(b,bit);
		}
		
		inline void intt(int* a,int bit,bool f=0){
			if(f)butterfly(a,bit);
			int lim=1<<bit;
			for(int k=0;k<bit;k++){
				i64 pw=1;
				for(int j=0;j<(1<<k)-1;j++,pw=pw*mod_iroot[k]%mod){
					for(int i=j;i<lim;i+=1<<(k+1)){
						int x=a[i],&y=(a[i^(1<<k)]=a[i^(1<<k)]*pw%mod);
						(a[i]+=y)<mod?0:a[i]-=mod;
						(y=x-y)<0?y+=mod:0;
					}
				}
				for(int i=(1<<k)-1;i<lim;i+=1<<(k+1)){
					int x=a[i],&y=(a[i^(1<<k)]=a[i^(1<<k)]*pw%mod);
					(a[i]+=y)<mod?0:a[i]-=mod;
					(y=x-y)<0?y+=mod:0;
				}
			}
			i64 iv=mod;iv<<=bit;iv=(iv-mod+1)>>bit;
			for(int i=0;i<lim;i++)
				a[i]=a[i]*iv%mod;
		}
	}using fast_number_theory_transform::ntt;
	using fast_number_theory_transform::intt;
}
using math::fsp;
using math::ntt;
using math::intt;
int n,m;
int a[262144],b[262144];
int main(){
// #ifndef DEBUG
// 	ios::sync_with_stdio(0);
// 	cin.tie(0);
// #endif
	n=gint();m=gint();
	for(int i=0;i<=n;i++)a[i]=gint();
	for(int i=0;i<=m;i++)b[i]=gint();
	int bit=__lg(n+m)+1;
	ntt(a,b,bit);
	for(int i=0;i<(1<<bit);i++)a[i]=1ll*a[i]*b[i]%mod;
	intt(a,bit);
	for(int i=0;i<=n+m;i++)pint(a[i]),iobuff::pchar(' ');
}

评测结果