基础知识
拉格朗日插值法
给你n个点((x_1,y_1),(x_2,y_2),...)
求一个n-1次的多项式(f(x))，求(f(k))
我们可以认为(f(x)=f_1(x)+f_2(x)+..+f_{n+1}(x))
其中(f_i(x_i)=y_i) 且 (forall j eq i,f_i(x_j)=0)
也就是说一个点(x_i)只在一个函数中为(y_i),其他函数中均为0
换言之就是把多条曲线合在一起（跟CRT的构造思想一致）
然后我们很容易构造以上式子
[f(x)=sum_{i=1}^{n}y_iPi_{j
eq i}frac{x-x_j}{x_i-x_j}
]
重心拉格朗日插值法
[f(x)=sum_{i=1}^{n}y_iPi_{j
eq i}frac{x-x_j}{x_i-x_j}
]
令
[g(x)=Pi_{i=1}^{n}x-x_i
]
[h(i)=frac{y_i}{Pi_{j!=i}x_i-x_j}
]
那么
[f(x)=g(x)sum_{i=1}^{n}frac{h(i)}{x-x_i}
]
那么如果我们要修改单点的横坐标，就可以单独修改(h(i),g(x))来解决，复杂度为(O(n))
FFT && NTT
FFT
NTT
对于NTT,只是把N次复数单位根换成了原根
泰勒级数，泰勒公式，泰勒展开
“使用泰勒公式进行估算时，在不同点展开的区别和意义是啥?”的回答
多项式全家桶
假设(A(x))已知
多项式牛顿迭代
求(G(B(x))equiv 0 mod x^n)
使用倍增法,设(frac{n}{2})项多项式(B_0(x))满足(G(B_0(x))equiv 0 mod x^{frac{n}{2}})
泰勒展开一波
[G(B(x))equiv frac{G(B_0(x))}{0!}+frac{G^{'}(B_0(x))}{1!}(B(x)-B_0(x))+frac{G^{''}(B_0(x))}{2!}(B(x)-B_0(x))^2··· (mod x^n)
]
可知(B(x))与(B_0(x))前(frac{n}{2})项相同，所以((B(x)-B_0(x))^k(kge 2))在模(x^n)意义下为0
所以
[B(x)equiv B_0(x)-frac{G(B_0(x))}{G^{'}(B_0{x})}
]
多项式求逆
假设我们已经推完了(A(x)B_0(x)equiv 1mod x^{n})
要求(A(x)B(x)equiv 1mod x^{2n})中的(B(x))
[egin{aligned}A(x)(B(x)-B_0(x))=0 mod x^{n}\B(x)-B_0(x)equiv0 mod x^n\B^2(x)-2B(x)B_0(x)+B_0^2(x)equiv 0 mod x^{2n}\B(x)-2B_0(x)+A(x)B_0^2(x)equiv 0 mod x^{2n}\B(x)equiv B_0(x)(2-A(x)B_0(x)) mod x^{2n}end{aligned}
]
多项式ln/exp
ln
[egin{aligned}B(x)&equivln A(x) mod x^n\&equivintfrac{A^{'}(x)}{A(x)}dx mod x^nend{aligned}
]
exp
[egin{aligned}B(x)equiv e^{A(x)} mod x^n \ln B(x)-A(x)equiv 0 mod x^n end{aligned}
]
设(G(B(x))=ln B(x)-A(x)) ，则(G^{'}(B(x))=frac{1}{B(x)})，套牛顿迭代公式
[egin{aligned}B(x)&equiv B_0(x)-frac{ln B_0(x)-A(x)}{frac{1}{B_0(x)}}\&equiv B_0(x)(1-ln B_0(x)+A(x))end{aligned}
]
多项式开方
牛顿迭代得
[B(x)=B_0(x)-frac{B_0^2(x)-A(x)}{2B_0(x)}
]
多项式快速幂
[egin{aligned}B(x)&equiv A^k(x)\&equiv e^{kln A(x) }end{aligned}
]
时间复杂度(O(nlogn))然而常数巨大
代码
int qpow(int x,int b){
int ans=1,mul=x;
while(b){
if(b&1)ans=1ll*ans*mul%MOD;
mul=1ll*mul*mul%MOD;
b>>=1;
}
return ans;
}
void NTT(int *a,int Len,int type){
for(int i=0;i<Len;i++)if(i<re[i])swap(a[i],a[re[i]]);
for(int mid=1;mid<Len;mid<<=1){
int Wn=qpow(type==1?gi:gf,(MOD-1)/(mid<<1));
for(int l=0;l<Len;l+=(mid<<1)){
int w=1;
for(int k=0;k<mid;k++,w=1ll*w*Wn%MOD){
int x=a[l+k],y=1ll*a[l+k+mid]*w%MOD;
a[l+k]=(x+y)%MOD;a[l+k+mid]=(x-y+MOD)%MOD;
}
}
}
if(type==-1){
int inv=qpow(Len,MOD-2);
for(int i=0;i<Len;i++)a[i]=1ll*a[i]*inv%MOD;
}
}
void Init(int n){
for(Len=1,N=0;Len<=(n<<1);Len<<=1,N++);
for(int i=0;i<Len;i++)re[i]=(re[i>>1]>>1)|((i&1)<<(N-1));
}
void get_Inv(int *f,int n,int *b){
if(n==1){
return b[0]=qpow(f[0],MOD-2),void();
}
get_Inv(f,(n+1)>>1,b);
Init(n);
for(int i=0;i<n;i++)a[i]=f[i];
for(int i=n;i<Len;i++)a[i]=0;
NTT(a,Len,1);NTT(b,Len,1);
for(int i=0;i<Len;i++)b[i]=1ll*(2-1ll*a[i]*b[i]%MOD+MOD)%MOD*b[i]%MOD;
NTT(b,Len,-1);
for(int i=n;i<Len;i++)b[i]=0;
return;
}
void get_Ln(int *f,int n,int *b){
memset(inv,0,sizeof(inv));
memset(la,0,sizeof(la));
for(int i=0;i<=n-2;i++)la[i]=1ll*f[i+1]*(i+1)%MOD;//mis
la[n-1]=0;
get_Inv(f,n,inv);
Init(n);
NTT(la,Len,1);NTT(inv,Len,1);
for(int i=0;i<Len;i++)b[i]=1ll*la[i]*inv[i]%MOD;
NTT(b,Len,-1);
for(int i=n-1;i>=1;i--)b[i]=1ll*b[i-1]*qpow(i,MOD-2)%MOD;//mis
b[0]=0;
}
void get_Exp(int *f,int deg,int *b){
if(deg==1)return b[0]=1,void();
get_Exp(f,(deg+1)>>1,b);
memset(ln,0,4*deg);
memset(ea,0,4*deg);
get_Ln(b,deg,ln);
// for(int i=0;i<deg;i++)printf("%d ",ln[i]);
// printf("
");
Init(deg);
for(int i=0;i<deg;i++)ea[i]=f[i];
for(int i=deg;i<Len;i++)ea[i]=0;
NTT(ea,Len,1);NTT(b,Len,1);NTT(ln,Len,1);
for(int i=0;i<Len;i++)b[i]=1ll*(1-ln[i]+ea[i]+MOD)%MOD*b[i]%MOD;
NTT(b,Len,-1);
for(int i=deg;i<Len;i++)b[i]=0;
}
void get_Pow(int *f,int deg,int k,int *b){
for(int i=0;i<deg;i++)pa[i]=f[i];
get_Ln(pa,deg,pa);
for(int i=0;i<deg;i++)pa[i]=1ll*pa[i]*k%MOD;
get_Exp(pa,deg,b);
}
void get_Sqrt(int *f,int n,int *b){
if(n==1)return b[0]=1,void();
get_Sqrt(f,(n+1)>>1,b);
memset(inv,0,sizeof(inv));
get_Inv(b,n,inv);
Init(n);
for(int i=0;i<n;i++)sa[i]=f[i];
for(int i=n;i<Len;i++)sa[i]=0;
NTT(sa,1);NTT(inv,1);
for(int i=0;i<Len;i++)
sa[i]=1ll*sa[i]*inv[i]%MOD;
NTT(sa,-1);
for(int i=0;i<Len;i++)b[i]=1ll*qpow(2,MOD-2)*(b[i]+sa[i])%MOD;
for(int i=n;i<Len;i++)b[i]=0;
}