多项式板子

namespace mypoly{
	const int MOD=998244353;
	const int g=3;
	int G[19][(1<<18)+1],R[19][(1<<18)+1];
	inline int quick(int A,int B){
		int res=1;
		while(B){
			if(B&1) res=1ll*res*A%MOD;
			A=1ll*A*A%MOD;
			B>>=1;
		}
		return res;
	}
	inline int inv(int x){
		return quick(x,MOD-2);
	}
	struct POLY{
		int len;
		int rev[1<<18];
		POLY(){
			rb(i,1,18){
				G[i][0]=1;
				R[i][0]=1;
				int tmp2=inv(quick(g,(MOD-1)>>i)); 
				int tmp=quick(g,(MOD-1)>>i);
				rb(j,1,(1<<i)){
					G[i][j]=1ll*G[i][j-1]*tmp%MOD;
					R[i][j]=1ll*R[i][j-1]*tmp2%MOD;
				}
			}
		}
		void butterfly(vector<int> & v){
			rep(i,len){
				rev[i]=rev[i>>1]>>1;
				if(i&1) rev[i]|=len>>1; 
			}
			rep(i,len) if(rev[i]>i) swap(v[i],v[rev[i]]);
		}
		vector<int> ntt(vector<int> v,int ty){
			for(auto & it: v){
				it%=MOD;
			}
			butterfly(v);
			vector<int> nex;
			int lg=1;
			for(int l=2;l<=len;l<<=1,++lg){
				nex.clear();
				nex.resize(len);
				for(int j=0;j<len;j+=l){
					for(int k=0;k<l/2;++k){
						int A,B;
						A=v[j+k];
						B=v[j+l/2+k];
						B=1ll*(ty==-1? R[lg][k]:G[lg][k])*B%MOD;
						nex[j+k]=(A+B)%MOD;
						nex[j+k+l/2]=(A-B+MOD)%MOD;
					}
				}
				v=nex;
			}
			return v;
		}
		void getlen(int x){
			len=1;
			while(len<x){
				len<<=1;
			}
		}
		vector<int> mul(vector<int> A,vector<int> B){
			getlen(A.size()+B.size());
			A.resize(len);
			B.resize(len);
			A=ntt(A,1);
			B=ntt(B,1);
			rep(i,len) A[i]=1ll*A[i]*B[i]%MOD;
			A=ntt(A,-1);
			int iv=inv(len);
			rep(i,len){
				A[i]=1ll*A[i]*iv%MOD;
			}
			while(!A.empty()&&A.back()==0) A.pop_back();
			return A;
		}
		vector<int> inverse(vector<int> A,int n){
			//计算% x^n 的逆元
			vector<int> ret(n);
			if(n==1){
				ret[0]=quick(A[0],MOD-2);
			}
			else{
				vector<int> oth=inverse(A,(n+1)>>1);
				ret=oth;
				ret.resize(n);
				rep(i,n) ret[i]=2ll*ret[i]%MOD;
				oth=mul(oth,oth);
				oth.resize(n);
				oth=mul(oth,A);
				oth.resize(n);
				rep(i,n) (ret[i]+=MOD-oth[i])%=MOD;
			}
			return ret;
		}
	}poly;
	inline vector<int> operator * (vector<int> A,vector<int> B){
		return poly.mul(A,B);
	}
	inline vector<int> operator + (vector<int> A,vector<int> B){
		int Sz=max(A.size(),B.size());
		A.resize(Sz);
		rep(i,B.size()) (A[i]+=B[i])%=MOD;
		return A;
	}
	inline vector<int> operator - (vector<int> A,vector<int> B){
		int Sz=max(A.size(),B.size());
		A.resize(Sz);
		rep(i,B.size()) (A[i]+=MOD-B[i])%=MOD;
		return A;
	}
	inline vector<int> operator / (vector<int> A,vector<int> B){
		while(A.size()!=1&&A.back()==0) A.POB();
		while(B.size()!=1&&B.back()==0) B.POB();
		vector<int> rem;
		int n,m;
		n=A.size()-1;
		m=B.size()-1;
		reverse(ALL(A));
		reverse(ALL(B));
		rem=A*poly.inverse(B,n-m+1);
		rem.resize(n-m+1);
		reverse(ALL(rem));
		return rem;
	}
	inline vector<int> operator % (vector<int> A,vector<int> B){
		while(A.size()!=1&&A.back()==0) A.POB();
		while(B.size()!=1&&B.back()==0) B.POB();
		if(B.size()>A.size()) return A;
		vector<int> mod=A-(A/B)*B;
		mod.resize(B.size()-1);
		while(mod.size()!=1&&mod.back()==0) mod.POB();
		return mod;
	}
	inline vector<int> der(vector<int> A){
		while(A.size()!=1&&A.back()==0) A.POB();
		vector<int> ret(A.size()-1);
		rep(i,ret.size()) ret[i]=1ll*(i+1)*A[i+1]%MOD; 
		if(ret.empty()) return vector<int> (1,0);
		return ret;
	}
	class MC{//多点求值 
		vector<vector<int> > RAM;
		vector<vector<int> > SIN;
		vector<int> Lc;
		vector<int> Rc;
		vector<int> ret;
		vector<int> x_;
		void fendge1(int l,int r,int& cnt){
			if(l==r-1){
				Lc.PB(0);
				Rc.PB(0);
				RAM.PB(SIN[l]);
				return ;
			}
			RAM.PB(vector<int> (0));
			Lc.PB(0);
			Rc.PB(0);
			int now=cnt;
			int mid=(l+r)>>1;
			int L=++cnt;
			fendge1(l,mid,cnt);
			int R=++cnt;
			fendge1(mid,r,cnt);
			Lc[now]=L;
			Rc[now]=R;
			RAM[now]=RAM[L]*RAM[R];
		}
		void fendge2(int l,int r,int cnt,vector<int> p){
			p=p%RAM[cnt];
			if(r-l<=650){
				rb(i,l,r-1){
					int T=1;
					rep(j,p.size()){
						(ret[i]+=1ll*T*p[j]%MOD)%=MOD;
						T=1ll*T*x_[i]%MOD;
					}
				}
				return ;
			}
			int mid=(l+r)>>1;
			fendge2(l,mid,Lc[cnt],p);
			fendge2(mid,r,Rc[cnt],p); 
		}
		public:
			vector<int> init(vector<int> p,vector<int> x){
				x_=x;
				Lc.clear();
				Rc.clear();
				RAM.clear();
				SIN.clear();
				ret.clear();
				ret.resize(x.size());
				rep(i,x.size()){
					SIN.PB(vector<int>{(MOD-x[i])%MOD,1});
				}
				int cnt=0;
				fendge1(0,x.size(),cnt);
				fendge2(0,x.size(),0,p);
				return ret;
			}
	}mc;
	vector<int> multiple_calculation(vector<int> p,vector<int> x){
		return mc.init(p,x);	
	}
	class ITP{
		vector<int> u;
		vector<int> v;
		vector<int> fm;
		vector<int> fendge(int l,int r){
			if(l==r-1){return vector<int> {(MOD-u[l])%MOD,1};}
			int mid=(l+r)>>1;
			return fendge(l,mid)*fendge(mid,r);
		}
		pair<vector<int>,vector<int> > fendge2(int l,int r){
			if(l==r-1){
				return {vector<int> {(MOD-u[l])%MOD,1},vector<int> {fm[l]}};
			}
			int mid=(l+r)>>1;
			pair<vector<int>,vector<int> > L,R;
			L=fendge2(l,mid);
			R=fendge2(mid,r);
			return {L.FIR*R.FIR,L.FIR*R.SEC+R.FIR*L.SEC}; 
		}
		public:
			vector<int> solve(vector<mp> x){
				u.clear();
				v.clear();
				int n=x.size();
				for(auto it:x) u.PB(it.FIR),v.PB(it.SEC);
				vector<int> g=fendge(0,u.size());
				fm=multiple_calculation(der(g),u);
				rep(i,n){
					fm[i]=1ll*v[i]*inv(fm[i])%MOD;
				}
				return fendge2(0,n).SEC;
			}
	}itp;
	vector<int> interpolation(vector<mp> x){
		return itp.solve(x);
	}
}

多项式板子

原文：https://www.cnblogs.com/gary-2005/p/14587395.html