多项式模板合集
在绞尽脑汁学习过后记下的一些笔记和代码……
我也只是半懂，(so) 这篇文章对初学者可能不太友好。
好的参考资料(来自 (Miskcoo's) (space) )：
从多项式乘法到快速傅里叶变换
多项式求逆元
多项式除法及求模
多项式的多点求值与快速插值
牛顿迭代法在多项式运算的应用
对于下述代码，“前置”代码：
#define P 998244353
int Pow_mod(int x,int y){
int ret=1;
while(y){
if(y&1) ret=1ll*ret*x%P;
x=1ll*x*x%P;
y>>=1;
}
return ret;
}
int Plus(int x,int y) { return x+y>=P ? x+y-P : x+y; }
int Minus(int x,int y) { return x>=y ? x-y : x-y+P; }
FFT/NTT
int l,r[N],X[N];
void ntt(int *A,int ty){
for(int i=0;i<l;i++) X[r[i]]=A[i];
for(int i=0;i<l;i++) A[i]=X[i];
for(int i=2;i<=l;i<<=1){
int wn=Pow_mod(3,(P-1)/i);
if(ty==-1) wn=Pow_mod(wn,P-2);
for(int j=0;j<l;j+=i){
int w=1;
for(int k=j;k<j+i/2;k++){
int t=1ll*w*A[k+i/2]%P;
A[k+i/2]=Minus(A[k],t);
A[k]=Plus(A[k],t);
w=1ll*w*wn%P;
}
}
}
if(ty==1) return;
int Inv=Pow_mod(l,P-2);
for(int i=0;i<l;i++) A[i]=1ll*A[i]*Inv%P;
}
多项式求逆
int C[N];
void inv(int *A,int *B,int x){
if(x==1) { B[0]=Pow_mod(A[0],P-2); return; }
inv(A,B,(x+1)>>1);
l=1;
while(l<2*x) l<<=1;
for(int i=1;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)*(l>>1));
for(int i=0;i<x;i++) C[i]=A[i];
for(int i=x;i<l;i++) C[i]=0;
ntt(C,1); ntt(B,1);
for(int i=0;i<l;i++) B[i]=Minus(2ll*B[i]%P,1ll*C[i]*B[i]%P*B[i]%P);
ntt(B,-1);
for(int i=x;i<l;i++) B[i]=0;
}
多项式除法&取模
void div(int *A,int *B,int *D,int *R){ //A[N]有n项,B[N]有m项。A[x]=B[x]*D[x]+R[x]
int Ar[N],Br[N],Dr[N];
for(int i=0;i<n;i++) Ar[i]=A[n-i-1];
for(int i=0;i<m;i++) Br[i]=B[m-i-1];
inv(Br,Dr,n-m+1);
l=1;
while(l<2*n) l<<=1;
for(int i=1;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)*(l>>1));
ntt(Dr,1); ntt(Ar,1);
for(int i=0;i<l;i++) Dr[i]=1ll*Dr[i]*Ar[i]%P;
ntt(Dr,-1);
for(int i=0;i<=n-m;i++) D[i]=Dr[n-m-i];
for(int i=0;i<m;i++) Br[i]=B[i];
ntt(Br,1); ntt(D,1);
for(int i=0;i<l;i++) Br[i]=1ll*Br[i]*D[i]%P;
ntt(Br,-1); ntt(D,-1);
for(int i=0;i<m-1;i++) R[i]=Minus(A[i],Br[i]);
}