代码

#include<bits/stdc++.h>
#define Inc(x,y) ((x+=y)>=mod&&(x-=mod))
#define Dec(x,y) ((x-=y)<0&&(x+=mod))
using namespace std;
const int mod=998244353;
const int gen=3,ivg=332748118;
const int N=1<<21|5;
namespace Math{
	inline int fmo(const int& x,const int& y){
		long long t=1ll*x*y;
		long long h=(t>>29)*2309898375ll>>32;
		t-=h*mod;return t>=mod?t-mod:t;
	}inline int fp(int x,int y){
		if(!x)return !y;int ans=1;
		for(;y&&x!=1;y>>=1,x=fmo(x,x))(y&1)&&(ans=fmo(ans,x));
		return ans;
}}namespace Poly{
	using Math::fp;using Math::fmo;
	struct lsp{int A[40],B[40];
		lsp(const int& x=gen){
			A[22]=fp(x,mod>>22);B[(1<<22)%37]=22;
			for(int i=22;i;i--)A[(i-1)]=fmo(A[i],A[i]),B[(1<<(i-1))%37]=i-1;
		}inline int operator ()(const int& x)const{return A[B[x%37]];}
	}PW_GEN;int pw[N],inited=0,rev[N];
	inline void initw(const int& x){
		inited=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
		for(int i=1;i<x;i<<=1){
			pw[i]=1;pw[i+1]=PW_GEN(i<<1);
			for(int j=2;j<i;j++)pw[i+j]=fmo(pw[i+j-1],pw[i+1]);
	}}inline void ntt(int *a,const int& lim,const int& fl=1){
		(inited!=lim)&&(initw(lim),0);
		for(int i=0;i<lim;i++)(i<rev[i])&&(swap(a[i],a[rev[i]]),0);
		for(int k=1;k<lim;k<<=1)
			for(int i=0;i<k;++i)
				for(int j=0;j<lim;j+=k<<1){
					int t=fmo(pw[i+k],a[i+j+k]);a[i+j+k]=a[i+j];
					Dec(a[i+j+k],t);Inc(a[i+j],t);
		}if(!fl){
			for(int iv=fp(lim,mod-2),i=0;i<lim;i++)a[i]=fmo(a[i],iv);
			reverse(a+1,a+lim);
	}}int A[N],B[N];
	#define bs basic_string<int>
	struct poly{
		bs f;int n;
		poly(const int *a=NULL,const int& x=0){
			f.resize(n=x);for(int i=0;i<n;i++)f[i]=a[i];
		}poly(const int& x){f.resize(n=1);f[0]=x;} 
		inline bs::iterator begin(){return f.begin();}
		inline bs::iterator end(){return f.end();}
		inline bs::reverse_iterator rbegin(){return f.rbegin();}
		inline bs::reverse_iterator rend(){return f.rend();}
		inline int size()const{return n;}
		inline void resize(const int &x){f.resize(n=x);} 
		inline int& operator [](const int& x){return f[x];}
		inline const int operator [](const int& x)const{return f[x];}
		inline const int *c_str()const{return f.c_str();}
		inline void getarrary(int *a)const{memcpy(a,f.c_str(),n<<2);}
		inline poly operator +(const poly& a)const{
			getarrary(A);a.getarrary(B);
			int m=max(n,a.n);for(int i=0;i<m;i++)Inc(A[i],B[i]);
			poly b=poly(A,m);for(int i=0;i<m;i++)A[i]=B[i]=0;return b;
		}inline poly operator -(const poly& a)const{
			getarrary(A);a.getarrary(B);
			int m=max(n,a.n);for(int i=0;i<m;i++)Dec(A[i],B[i]);
			poly b=poly(A,m);for(int i=0;i<m;i++)A[i]=B[i]=0;return b;
		}inline poly operator *(const poly& a)const{
			getarrary(A);a.getarrary(B);
			int lim=1;while(lim<n+a.n)lim<<=1;ntt(A,lim);ntt(B,lim);
			for(int i=0;i<lim;i++)A[i]=fmo(A[i],B[i]);ntt(A,lim,0);
			poly b=poly(A,n+a.n-1);for(int i=0;i<lim;i++)A[i]=B[i]=0;return b;
		}inline poly operator *(const int& x)const{
			getarrary(A);for(int i=0;i<n;i++)A[i]=fmo(A[i],x);
			poly a=poly(A,n);for(int i=0;i<n;i++)A[i]=0;return a;
		}inline poly getpoly(const int& x)const{
			poly a;a.resize(x);for(int i=0;i<n&&i<x;i++)a[i]=f[i];return a;
		}inline poly inv()const{
			poly a(fp(f[0],mod-2));
			for(int i=1;i<n;i<<=1){
				a=a*2-a*a*getpoly(i<<1);
				a.resize(i<<1);
			}a.resize(n);return a;
		}inline poly rev()const{
			poly a=*this;reverse(a.begin(),a.end());return a;
		}inline poly operator /(const poly& a)const{
			poly b=(rev()*a.rev().getpoly(n).inv());b.resize(n-a.n+1);reverse(b.begin(),b.end());return b;
		}inline poly operator %(const poly& a)const{poly b=(*this)-(*this)/a*a;b.resize(a.n-1);return b;}
	};
	#undef bs
}
using Poly::poly;
int f[N],g[N],n,m;
poly F,G,H,T;
int main(){
	scanf("%d%d",&n,&m);++n;++m;
	for(int i=0;i<n;i++)scanf("%d",f+i);
	for(int i=0;i<m;i++)scanf("%d",g+i);
	F=poly(f,n);G=poly(g,m);H=F/G;T=F%G;
	for(int i=0;i<H.n;i++)printf("%d ",H[i]);puts("");
	for(int i=0;i<T.n;i++)printf("%d ",T[i]);
	return 0;
}

评测结果