代码

#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
const int gen=3;
const int N=4e5+5;
inline bool isnum(const char &ch){return ch>='0'&ch<='9';}
inline int rd(){
	int x=0,fl=1;char ch;
	while(!isnum(ch=getchar()))fl=ch=='-'?-1:1;
	for(x=ch^48;isnum(ch=getchar());x=(x<<1)+(x<<3)+(ch^48));
	return x*fl;
}
inline int fp(int x,int y,int mod=p){
	int ans=1;for(;y;y>>=1){
		if(y&1)ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;
	}
	return ans;
}
namespace Poly{
	int A[N],B[N],rev[N];
	inline void vclear(int *a,int n){for(int i=0;i<=n;i++)a[i]=0;}
	inline void ntt(int *a,int lim,int fl=1){
		for(int i=0;i<lim;i++){
			rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
			if(i<rev[i])swap(a[i],a[rev[i]]);
		}
		for(int k=1;k<lim;k<<=1){
			int o=fp(gen,(p-1)/(k<<1));if(!fl)o=fp(o,p-2);
			for(int j=0;j<lim;j+=k<<1)
				for(int i=j,w=1;i<j+k;i++,w=1ll*w*o%p){
					int t=1ll*a[i+k]*w%p;
					a[i+k]=(a[i]+p-t)%p;
					a[i]=(a[i]+t)%p;
				}
		}
		if(!fl)for(int i=0,iv=fp(lim,p-2);i<lim;i++)a[i]=1ll*a[i]*iv%p;
	}
	struct poly{
		vector<int>f;
		inline int siz(){return f.size();}
		inline int deg(){return f.size()-1;}
		inline int &operator[](const int& i){assert(i<siz());return f[i];}
		poly(int n=0){f.clear();for(int i=0;i<n;i++)f.push_back(0);}
		poly(int *a,int n){f.clear();for(int i=0;i<n;i++)f.push_back(a[i]);}
		inline void getv(int *a){for(int i=0;i<siz();i++)a[i]=f[i];}
		inline poly getp(int n){
			if(n>siz()){
				getv(A);poly a=poly(A,n);vclear(A,siz());
				return a;
			}
			for(int i=0;i<n;i++)A[i]=f[i];
			poly a=poly(A,n);vclear(A,n);
			return a;
		}
		inline poly operator + (poly a){
			getv(A);a.getv(B);int n=max(siz(),a.siz());
			for(int i=0;i<n;i++)A[i]=(A[i]+B[i])%p;
			a=poly(A,n);vclear(A,n);vclear(B,a.siz());
			return a;
		}
		inline poly operator - (poly a){
			getv(A);a.getv(B);int n=max(siz(),a.siz());
			for(int i=0;i<n;i++)A[i]=(A[i]+p-B[i])%p;
			a=poly(A,n);vclear(A,n);vclear(B,a.siz());
			return a;
		}
		inline poly operator * (poly a){
			getv(A);a.getv(B);int lim=1;while(lim<siz()+a.siz())lim<<=1;
			ntt(A,lim);ntt(B,lim);for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%p;
			ntt(A,lim,0);a=poly(A,siz()+a.siz()-1);vclear(A,lim);vclear(B,lim);
			return a;
		}
		inline poly operator * (const int& x){
			poly a;for(int i=0;i<siz();i++)a.f.push_back(1ll*f[i]*x%p);
			return a;
		}
		inline friend poly operator * (const int& x,poly a){
			for(int i=0;i<a.siz();i++)a[i]=1ll*a[i]*x%p;
			return a;
		}
		inline poly inv(){
			poly a=poly(1);a[0]=fp(f[0],p-2);
			for(int i=1;i<siz();i<<=1)
				a=a*2-((getp(i<<1)*a).getp(i<<1)*a).getp(i<<1);
			return a.getp(siz());
		}
		inline poly rev(){
			getv(A);for(int i=0;(i<<1|1)<siz();i++)swap(A[i],A[siz()-i-1]);
			poly a=poly(A,siz());vclear(A,siz());return a;
		}
		inline poly der(){
			for(int i=0;i<siz()-1;i++)A[i]=1ll*(i+1)*f[i+1]%p;
			poly a=poly(A,siz()-1);vclear(A,siz());return a;
		}
		inline poly ite(){
			B[1]=1;A[1]=f[0];
			for(int i=2;i<=siz();i++){
				B[i]=1ll*(p-p/i)*B[p%i]%p;
				A[i]=1ll*B[i]*f[i-1]%p;
			}
			poly a=poly(A,siz()+1);vclear(A,siz());vclear(B,siz());
			return a;
		}
		inline poly ln(){return (der()*inv()).getp(siz()-1).ite();}
		inline poly operator /(poly& a){
			if(siz()<a.siz())return poly();
			int n=siz()-a.siz()+1;
			return (rev().getp(n)*a.rev().getp(n).inv()).getp(n).rev();
		}
		inline poly operator %(poly& a){
			if(siz()<a.siz())return *this;
			return (*this-(*this/a)*a).getp(a.siz()-1);
		}
	};
}
using Poly::poly;
poly a,b,c,d;
int n,m,f[N],g[N];
int main(){
	n=rd();m=rd();
	for(int i=0;i<=n;i++)f[i]=rd()%p;
	for(int i=0;i<=m;i++)g[i]=rd()%p;
	a=poly(f,n+1);b=poly(g,m+1);
	c=a/b;d=(a-b*c).getp(m);
	for(int i=0;i<c.siz();i++)printf("%d ",c[i]);
	puts("");
	for(int i=0;i<d.siz();i++)printf("%d ",d[i]);
	return 0;
}

评测结果