多项式板子

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=262150,mod=998244353,g=3,invg=(mod+1)/3,inv2=(mod+1)/2;
int rev[N];
ull a[N],b[N],w[N],inv[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=1ll*ans*a%mod;
		}
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
void CLR(ull *a,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=0;
	}
}
void CPY(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=b[i];
	}
}
void INIT(int lim){
	for(int i=0;i<lim;i++){
		rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
	}
}
void REV(ull *a,int n){
	reverse(a,a+n);
}
void ADD(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=(a[i]+b[i])%mod;
	}
}
void DEC(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=(a[i]-b[i]+mod)%mod;
	}
}
void DRV(ull *a,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=a[i+1]*(i+1)%mod;
	}
}
void ITG(ull *a,int n){
	for(int i=n-1;i>=1;i--){
		a[i]=a[i-1]*inv[i]%mod;
	}
	a[0]=0;
}
void NTT(ull *a,int lim,int op){
	ull x,y;
	int r;
	for(int i=0;i<lim;i++){
		if(i<rev[i]){
			swap(a[i],a[rev[i]]);
		}
	}
	w[0]=1;
	for(int mid=1;mid<lim;mid<<=1){
		r=mid<<1;
		x=qpow(op==1?g:invg,(mod-1)/r);
		for(int j=1;j<mid;j++){
			w[j]=w[j-1]*x%mod;
		}
		for(int j=0;j<lim;j+=r){
			for(int k=j;k-j<mid;k++){
				x=a[k];
				y=a[k+mid]%mod*w[k-j]%mod;
				a[k]=x+y;
				a[k+mid]=x-y+mod;
			}
		}
		if(mid==(1<<18)){
			for(int j=0;j<lim;j++){
				a[j]%=mod;
			}
		}
	}
	for(int i=0;i<lim;i++){
		a[i]%=mod;
	}
}
void CROSS(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=a[i]*b[i]%mod;
	}
}
void MUL(ull *a,ull *b,int n){
	int lim=1,invv;
	while(lim<n){
		lim<<=1;
	}
	invv=qpow(lim,mod-2);
	INIT(lim);
	NTT(a,lim,1);
	if(a!=b){
		NTT(b,lim,1);
	}
	CROSS(a,b,lim);
	NTT(a,lim,-1);
	for(int i=0;i<lim;i++){
		a[i]=a[i]*invv%mod;
	}
	CLR(a+n,lim-n-1);
	if(a!=b){
		CLR(b,lim);
	}
}
void INV(ull *a,ull *b,int n){
	int lim=1,l=0,invv;
	static ull c[N],d[N];
	b[0]=qpow(a[0],mod-2);
	while(lim<n){
		lim<<=1;
		l++;
	}
	for(int len=2;len<=lim;len<<=1){
		CLR(c+(len>>1),len>>1);
		CPY(c,b,len>>1);
		CPY(d,a,len);
		INIT(len);
		NTT(c,len,1);
		NTT(d,len,1);
		CROSS(d,c,len);
		NTT(d,len,-1);
		invv=qpow(len,mod-2);
		for(int i=0;i<len;i++){
			d[i]=d[i]*invv%mod;
		}
		CLR(d,len>>1);
		NTT(d,len,1);
		CROSS(d,c,len);
		NTT(d,len,-1);
		for(int i=len>>1;i<len;i++){
			b[i]=mod-d[i]*invv%mod;
		}
	}
	for(int i=0;i<lim;i++){
		b[i]%=mod;
	}
	CLR(b+n,lim-n-1);
}
int BSGS(int b,int n,int mod){
	int t=sqrt(mod)+1,now=1;
	unordered_map<int,int>mapp;
	for(int bb=0;bb<=t-1;bb++){
		mapp[1ll*now*n%mod]=bb;
		now=1ll*now*b%mod;
	}
	b=now;
	now=1;
	for(int aa=1;aa<=t;aa++){
		now=1ll*now*b%mod;
		if(mapp.count(now)){
			return aa*t-mapp[now];
		}
	}
	return -1;
}
void SQRT(ull *a,ull *b,int n){
	int lim=1,l=0;
	static ull c[N],d[N];
	b[0]=qpow(g,BSGS(g,a[0],mod)/2);
	b[0]=min(b[0],mod-b[0]);
	while(lim<n){
		lim<<=1;
		l++;
	}
	for(int len=2;len<=lim;len<<=1){
		CPY(c,b,len);
		CLR(d,len);
		INV(c,d,len);
		CLR(c,len);
		CPY(c,a,len);
		MUL(c,d,len<<1);
		ADD(b+(len>>1),c+(len>>1),len>>1);
		for(int i=len>>1;i<len;i++){
			b[i]=b[i]*inv2%mod;
		}
	}
}
void DIV(ull *a,ull *b,int n,int m){
	static ull c[N],d[N];
	REV(a,n);
	REV(b,m);
	CPY(c,b,n-m+1);
	INV(c,d,n-m+1);
	CPY(c,a,n-m+1);
	MUL(c,d,(n-m+1)<<1);
	CLR(c+n-m+1,n-m+1);
	REV(c,n-m+1);
	CPY(d,c,n-m+1);
	REV(a,n);
	REV(b,m);
	MUL(c,b,n<<1);
	CLR(c+n,n);
	DEC(a,c,n);
	CPY(b,a,m-1);
	CPY(a,d,n-m+1);
}
void LN(ull *a,ull *b,int n){
	static ull c[N];
	CPY(b,a,n);
	DRV(b,n);
	INV(a,c,n);
	MUL(b,c,n<<1);
	CLR(b+n,n);
	ITG(b,n);
}
void EXP(ull *a,ull *b,int n){
	int lim=1;
	static ull c[N],d[N];
	b[0]=1;
	while(lim<n){
		lim<<=1;
	}
	for(int len=2;len<=lim;len<<=1){
		CPY(c,b,len);
		CLR(d,len);
		LN(c,d,len);
		CLR(c,len);
		c[0]=1;
		DEC(c,d,len);
		ADD(c,a,len);
		MUL(b,c,len<<1);
		CLR(b+len,len);
		CLR(c+len,len);
	}
}
void POW(ull *a,int n,int k){
	static ull b[N];
	LN(a,b,n);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*k%mod;
	}
	CLR(a,n);
	EXP(b,a,n);
	CLR(b,n);
}
void SIN(ull *a,ull *b,int n){
	int ii;
	static ull c[N],d[N]; 
	CPY(c,a,n);
	ii=qpow(g,BSGS(g,mod-1,mod)/2);
	for(int i=0;i<=n-1;i++){
		c[i]=c[i]*ii%mod;
	}
	EXP(c,b,n);
	CPY(d,b,n);
	CLR(c,n);
	INV(d,c,n);
	DEC(b,c,n);
	ii=qpow(ii,mod-2);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*inv2%mod*ii%mod;
	}
}
void COS(ull *a,ull *b,int n){
	int ii;
	static ull c[N],d[N];
	CPY(c,a,n);
	ii=qpow(g,BSGS(g,mod-1,mod)/2);
	for(int i=0;i<=n-1;i++){
		c[i]=c[i]*ii%mod;
	}
	EXP(c,b,n);
	CPY(d,b,n);
	CLR(c,n);
	INV(d,c,n);
	ADD(b,c,n);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*inv2%mod;
	}
}
void ARCSIN(ull *a,ull *b,int n){
	static ull c[N],d[N];
	CPY(b,a,n);
	DRV(b,n);
	CPY(c,a,n);
	MUL(c,c,n<<1);
	CLR(c+n,n);
	d[0]=1;
	DEC(d,c,n);
	CLR(c,n);
	SQRT(d,c,n);
	CLR(d,n);
	INV(c,d,n);
	MUL(b,d,n<<1);
	CLR(b+n,n);
	ITG(b,n);
	CLR(c,n<<1);
	CLR(d,n);
}
void ARCTAN(ull *a,ull *b,int n){
	static ull c[N],d[N];
	CPY(b,a,n);
	DRV(b,n);
	CPY(c,a,n);
	MUL(c,c,n<<1);
	CLR(c+n,n);
	d[0]=1;
	ADD(d,c,n);
	CLR(c,n);
	INV(d,c,n);
	MUL(b,c,n<<1);
	CLR(b+n,n);
	ITG(b,n);
	CLR(c,n<<1);
	CLR(d,n);
}
int main(){
	inv[1]=1;
	for(int i=2;i<=n;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	}
	//do something...
}