多项式全家桶

还有好一些困难东西没学，现就这样吧。

每日一遍：\(167772161,469762049\)

除了求逆其他都要预留两倍空间！

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const ll N=(1<<19)+3,H=998244353,g=3,ig=(H+1)/3;
int U[N];
ull W[N];
ll Ksm(ll x,ll y=H-2)
{
	ll s=1;
	for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
	return s;
}
void Init(int L){for(int i=0;i<L;i++)U[i]=U[i/2]/2|(i&1?L/2:0);}
void Clr(ull *A,int l,int r){memset(A+l,0,(r-l+1)<<3);}
void Cpy(ull *A,ull *B,int l,int r){memcpy(A+l,B+l,(r-l+1)<<3);}
void Cro(ull *A,ull *B,int L){for(int i=0;i<L;i++)A[i]=A[i]*B[i]%H;}
void Neg(ull *A,int l,int r){for(int i=l;i<=r;i++)A[i]=!A[i]?0:H-A[i];}
void Dlt(ull *A,int L){for(int i=1;i<=L;i++)A[i-1]=A[i]*i%H;A[L]=0;}
void Sum(ull *A,int L){for(int i=L;i>0;i--)A[i]=A[i-1]*Ksm(i)%H;A[0]=0;}
void Add(ull *A,ull *B,int L){for(int i=0;i<=L;i++)A[i]=(A[i]+B[i])%H;}
void Mul(ull *A,int L,ll d){for(int i=0;i<=L;i++)A[i]=A[i]*d%H;}
void Rev(ull *A,int L){reverse(A,A+L+1);}
void NTT(ull *p,int L,int op)
{
	for(int i=0;i<L;i++)if(i<U[i])swap(p[i],p[U[i]]);
	for(int k=2,r=1;k<=L;r=k,k<<=1)
	{
		ull w=Ksm(op==1?g:ig,(H-1)/k),x;W[0]=1;
		for(int i=1;i<=r;i++)W[i]=W[i-1]*w%H;
		for(int i=0;i<L;i+=k)for(int l=i;l<i+r;l++)
			x=W[l-i]*p[l+r]%H,p[l+r]=p[l]-x+H,p[l]+=x;
		if(k==1<<16)for(int i=0;i<L;i++)p[i]%=H;
	}
	for(int i=0;i<L;i++)p[i]%=H;
	if(op==-1)for(ll i=0,j=Ksm(L);i<L;i++)p[i]=p[i]*j%H;
}
int Ceil(int n){int L=1;while(L<=n)L*=2;return L;}
void Mul(ull *A,int n,ull *B,int m)
{
	int L=Ceil(n+m);Init(L);
	NTT(A,L,1);NTT(B,L,1);
	Cro(A,B,L);NTT(A,L,-1);
}
void Inv(ull *F,int n)
{
	ull G[N],A[N],B[N];int L=Ceil(n);
	Clr(G,0,L);Clr(A,0,L);Clr(B,0,L);
	G[0]=Ksm(F[0]);
	for(int k=2,r=1;k<=L;r=k,k<<=1)
	{
		Cpy(A,G,0,r-1);Clr(A,r,k-1);Cpy(B,F,0,k-1);
		Init(k);NTT(A,k,1);NTT(B,k,1);Cro(B,A,k);NTT(B,k,-1);
		Clr(B,0,r-1);NTT(B,k,1);Cro(B,A,k);NTT(B,k,-1);
		Neg(B,r,k-1);Cpy(G,B,r,k-1);
	}
	Cpy(F,G,0,n);
}
void Ln(ull *F,int n)
{
	ull G[N];Clr(G,0,2*Ceil(n));
	Cpy(G,F,0,n);Inv(G,n);Dlt(F,n);
	Mul(F,n,G,n);Sum(F,n);
}
void Exp(ull *F,int n)
{
	ull G[N],A[N],B[N];int L=Ceil(n);
	Clr(G,0,2*L);Clr(A,0,2*L);Clr(B,0,2*L);
	G[0]=1;
	for(int k=2,r=1;k<=L;r=k,k<<=1)
	{
		Cpy(A,G,0,r-1);Clr(A,r,k-1);Cpy(B,G,0,r-1);
		Ln(A,k-1);Neg(A,0,k-1);Add(A,F,k-1);
		Mul(A,k-1,B,k-1);Cpy(G,A,r,k-1);
	}
	Cpy(F,G,0,n);
}
void Pow(ull *F,int n,ll k){Ln(F,n);Mul(F,n,k);Exp(F,n);}
void Ksm(ull *F,int n,ll k,ll _k,ll sz)
{
	ll p=0;
	while(p<=n&&!F[p])p++;
	if(p>n||p*k>n||(p&&sz>6)){Clr(F,0,n);return;}
	ll c=Ksm(F[p],_k),d=Ksm(F[p]);
	for(int i=0;i+p<=n;i++)F[i]=F[i+p]*d%H;
	Clr(F,n-p+1,n);Pow(F,n-p,k);
	for(int i=n-p*k;i>=0;i--)F[i+p*k]=F[i]*c%H;
	Clr(F,0,p*k-1);
}
void SSqrt(ull *F,int n)
{
	ull G[N],A[N],B[N];int L=Ceil(n);
	Clr(G,0,2*L);Clr(A,0,2*L);Clr(B,0,2*L);
	G[0]=1;
	for(int k=2,r=1;k<=L;r=k,k<<=1)
	{
		Cpy(A,G,0,r-1);Clr(A,r,k-1);Cpy(B,F,0,k-1);
		Inv(A,k-1);Mul(A,k-1,B,k-1);
		Mul(A,k-1,(H+1)/2);Cpy(G,A,r,k-1);
	}
	Cpy(F,G,0,n);
}
ll BSGS(ll a,ll b,ll p)
{
	ll A=1,B=sqrt(p)+1;unordered_map<ll,ll>mp;
	for(ll i=1;i<=B;i++)mp[(A=A*a%p)*b%p]=i;
	for(ll i=1,C=A;i<=B;i++,C=C*A%p)if(mp.count(C))return i*B-mp[C];
	return -1;
}
ll SqrtVal(ll x,ll k){ll y=Ksm(g,BSGS(g,x,H)/k);return min(y,H-y);}
void Sqrt(ull *F,int n)
{
	ll x=SqrtVal(F[0],2);Mul(F,n,Ksm(F[0]));
	SSqrt(F,n);Mul(F,n,x); 
}
void Div(ull *F,int n,ull *G,int m)
{
	ull A[N],B[N];int L=Ceil(n+m);
	Clr(A,0,L);Clr(B,0,L);
	Cpy(A,F,0,n);Cpy(B,G,0,m);
	Rev(A,n);Rev(B,m);Inv(B,n-m);
	if(n-m+1<=m)Clr(B,n-m+1,m);
	Mul(A,n,B,n-m);Clr(A,n-m+1,L);
	Rev(A,n-m);Cpy(B,A,0,n-m);
	Mul(A,n-m,G,m);Neg(A,0,n);Add(A,F,n);
	Clr(F,0,n);Clr(G,0,m);
	Cpy(F,B,0,n-m);Cpy(G,A,0,m-1);
}