多项式板子
cpp
namespace Poly{
using poly=vector<int>;
vector<int> rev;
const int P=998244353;
int qpow(int a,int b){
int ans=1;
for(;b;b>>=1){
if(b&1)ans=ans*a%P;
a=a*a%P;
}
return ans;
}
int bit=0,tot,g=3,gi=qpow(g,P-2);
void ntt(poly &a,int inv){
for(int i=0;i<tot;i++){
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(int mid=1;mid<tot;mid<<=1){
int g1=qpow(inv==1?g:gi,(P-1)/(mid*2));
for(int i=0;i<tot;i+=mid*2){
int gk=1;
for(int j=0;j<mid;j++,gk=gk*g1%P){
auto x=a[i+j],y=gk*a[i+j+mid]%P;
a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
}
}
}
if(inv==-1){
int invn=qpow(tot,P-2);
for(int i=0;i<tot;i++)a[i]=a[i]*invn%P;
}
}
void init(int n){
bit=0;
while((1<<bit)<n)bit++;
tot=1<<bit;
rev.resize(tot);
for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
// 多项式乘法
poly mul(poly a,poly b){
int n=a.size(),m=b.size();
init(n+m+1);
a.resize(tot),b.resize(tot);
ntt(a,1),ntt(b,1);
for(int i=0;i<tot;i++)a[i]=a[i]*b[i]%P;
ntt(a,-1);
for(int i=n+m;i<tot;i++)a[i]=0;
return a;
}
// 多项式求逆
poly inv(const poly &f,int n){
if(n==1)return {qpow(f[0],P-2)};
auto g=inv(f,n+1>>1);
static vector<int> c;
init(2*n+1);
c.resize(tot);
g.resize(tot);
for(int i=0;i<n;i++)c[i]=f[i];
for(int i=n;i<tot;i++)c[i]=0;
ntt(c,1),ntt(g,1);
for(int i=0;i<tot;i++)g[i]=g[i]*(2-c[i]*g[i]%P+P)%P;
ntt(g,-1);
for(int i=n;i<tot;i++)g[i]=0;
return g;
}
// 多项式求导
poly der(const poly &f){
int n=f.size();
poly g(n-1);
for(int i=1;i<n;i++)g[i-1]=f[i]*i%P;
return g;
}
// 多项式求积分
poly inte(const poly &f){
int n=f.size();
poly g(n+1);
g[0]=0;
for(int i=1;i<=n;i++)g[i]=f[i-1]*qpow(i,P-2)%P;
return g;
}
// 多项式求值
int eval(const poly &f,int x){
int n=f.size(),ans=0;
for(int i=n-1;i>=0;i--)ans=(ans*x+f[i])%P;
return ans;
}
// 多项式翻转Ar(x)=x^n*A(1/x)
poly reverse(const poly &f,int n){
poly g(n);
for(int i=0;i<n;i++)g[i]=f[n-i-1];
return g;
}
// 多项式加法
poly add(const poly &f,const poly &g){
poly c(max(f.size(),g.size()));
for(int i=0;i<max(f.size(),g.size());i++){
if(i<f.size())c[i]=f[i];
if(i<g.size())c[i]=(c[i]+g[i])%P;
}
return c;
}
// 多项式减法
poly sub(const poly &f,const poly &g){
poly c(max(f.size(),g.size()));
for(int i=0;i<max(f.size(),g.size());i++){
if(i<f.size())c[i]=f[i];
if(i<g.size())c[i]=(c[i]-g[i]+P)%P;
}
return c;
}
// 多项式除法
pair<poly,poly> div(const poly &f,const poly &g){
int n=f.size(),m=g.size(),len=n-m+1;
if(n<m)return {{},f};
poly fr=reverse(f,n),gr=reverse(g,m);
gr.resize(len);
for(int i=len;i<m;i++)gr[i]=0;
gr=inv(gr,len);
poly q=mul(fr,gr);
q=reverse(q,len);
poly r=sub(f,mul(q,g));
return {q,r};
}
// cipolla
int cipolla(int x){
if(qpow(x,P-1>>1)==P-1)return -1;
while(1){
int a=rng()%P;
int w=(a*a%P-x+P)%P;
auto mul=[&](PII a,PII b){
return PII{(a.F*b.F%P+w*a.S%P*b.S%P)%P,(a.F*b.S%P+a.S*b.F%P)%P};
};
auto pow=[&](PII a,int b){
PII res{1,0};
for(;b;b>>=1){
if(b&1)res=mul(res,a);
a=mul(a,a);
}
return res.F;
};
if(qpow(w,P-1>>1)==P-1){
int res=pow(PII{a,1},P+1>>1);
return min(res,P-res);
}
}
}
// 多项式开根(a0!=1)
poly sqrt(const poly &f,int n){
if(n==1){
if(f[0]==1)return {1};
return {cipolla(f[0])};
}
auto g=sqrt(f,n+1>>1);
static vector<int> c;
static const int inv2=qpow(2,P-2);
init(2*n+1);
c.resize(tot);
g.resize(tot);
for(int i=0;i<n;i++)c[i]=f[i];
for(int i=n;i<tot;i++)c[i]=0;
auto ig=inv(g,n);
ntt(g,1),ntt(ig,1),ntt(c,1);
for(int i=0;i<tot;i++)g[i]=(g[i]*g[i]%P+c[i])%P*ig[i]%P*inv2%P;
ntt(g,-1);
for(int i=n;i<tot;i++)g[i]=0;
return g;
}
// 多项式对数ln
poly ln(const poly &f){
return inte(mul(der(f),inv(f,f.size())));
}
// 多项式指数exp
poly exp(const poly &f,int n){
if(n==1)return {1};
poly g=exp(f,n+1>>1);
g.resize(n);
poly lng=ln(g);
init(2*n+1);
g.resize(tot);
lng.resize(tot);
for(int i=0;i<n;i++)lng[i]=(f[i]-lng[i]+P)%P;
for(int i=n;i<tot;i++)lng[i]=g[i]=0;
lng[0]++;
ntt(lng,1);
ntt(g,1);
for(int i=0;i<tot;i++)g[i]=g[i]*lng[i]%P;
ntt(g,-1);
for(int i=n;i<tot;i++)g[i]=0;
return g;
}
// 多项式快速幂
poly qpow(const poly &f,int b){
int n=f.size();
poly res{1},a=f;
res[0]=1;
init(n<<1);
res.resize(tot);
a.resize(tot);
for(;b;b>>=1){
ntt(a,1);
if(b&1){
ntt(res,1);
for(int i=0;i<tot;i++)res[i]=res[i]*a[i]%P;
ntt(res,-1);
for(int i=n;i<tot;i++)res[i]=0;
}
for(int i=0;i<tot;i++)a[i]=a[i]*a[i]%P;
ntt(a,-1);
for(int i=n;i<tot;i++)a[i]=0;
}
return res;
}
// 多项式多点求值
vector<int> evals(const poly &f,vector<int> &x){
vector<poly> T;
int n=f.size(),m=x.size();
T.assign(m<<2,{});
function<void(int,int,int)> build=[&](int p,int l,int r){
if(l==r){
T[p]={(P-x[l])%P,1};
return;
}
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
T[p]=mul(T[p<<1],T[p<<1|1]);
while(T[p].size()>1&&T[p].back()==0)T[p].pop_back();
};
vector<int> res(m);
function<void(int,int,int,poly)> solve=[&](int p,int l,int r,poly f){
if(r-l+1<=64){
for(int i=l;i<=r;i++){
res[i]=eval(f,x[i]);
}
return;
}
auto [q1,r1]=div(f,T[p<<1]);
auto [q2,r2]=div(f,T[p<<1|1]);
while(r1.size()>1&&r1.back()==0)r1.pop_back();
while(r2.size()>1&&r2.back()==0)r2.pop_back();
int mid=l+r>>1;
solve(p<<1,l,mid,r1);
solve(p<<1|1,mid+1,r,r2);
};
build(1,0,m-1);
if(f.size()>=T[1].size()){
auto [q,r]=div(f,T[1]);
solve(1,0,m-1,r);
}
else solve(1,0,m-1,f);
return res;
}
}