多项式模板整理
多项式乘法
1 inline void NTT(int *A,int tag) 2 { 3 FOR(i,0,lim-1) if (i<rev[i]) swap(A[i],A[rev[i]]); 4 for (register int mid=1;mid<lim;mid<<=1) 5 { 6 int Wn=qpow(g,(mod-1)/(mid<<1)); 7 if (tag==-1) Wn=qpow(Wn,mod-2); 8 for (register int Len=mid<<1,l=0;l<lim;l+=Len) 9 { 10 int w=1; 11 for (register int k=0;k<mid;k++,w=1LL*w*Wn%mod) 12 { 13 int x=A[l+k],y=1LL*w*A[l+mid+k]%mod; 14 A[l+k]=(1LL*x+y)%mod; 15 A[l+k+mid]=(1LL*x-y+mod)%mod; 16 } 17 } 18 } 19 if (tag==-1) 20 { 21 int inv=qpow(lim,mod-2); 22 FOR(i,0,lim-1) A[i]=1LL*A[i]*inv%mod; 23 } 24 return; 25 }
多项式求逆
$$A*B \equiv 1 ( \mod x^n)$$
$$A*B' \equiv 1( \mod x^{\frac{n}{2}})$$
$$A*(B-B') \equiv 0 (\mod x^{\frac{n}{2}})$$
$$B^2-2BB'+B'^2 \equiv0( \mod x^n)$$
$$B-2AB'+AB'^2\equiv0( \mod x^n)$$
$$B\equiv B'(2A-AB') ( \mod x^n)$$
1 inline void Get_inv(int *A,int *B,int n_tmp) 2 { 3 if (n_tmp==1) 4 { 5 B[0]=qpow(A[0],mod-2); 6 return; 7 } 8 int Base=(n_tmp+1)>>1; 9 Get_inv(A,B,Base); 10 Cal_rev(n_tmp); 11 FOR(i,0,Base-1) Tmp3[i]=B[i];FOR(i,Base,lim-1) Tmp3[i]=0; 12 FOR(i,0,n_tmp-1) Tmp4[i]=A[i];FOR(i,n_tmp,lim-1) Tmp4[i]=0; 13 NTT(Tmp3,1),NTT(Tmp4,1); 14 FOR(i,0,lim-1) Tmp3[i]=1LL*Tmp3[i]*(mod+2-1LL*Tmp3[i]*Tmp4[i]%mod)%mod; 15 NTT(Tmp3,-1); 16 FOR(i,0,n_tmp-1) B[i]=Tmp3[i],Tmp3[i]=Tmp4[i]=0; 17 return; 18 }
多项式取对数（ln）
$$B(x)=\ln A(x)$$
$$B'(x)=\frac{A'(x)}{A(x)}$$
1 inline void Get_dao(int *A,int *B,int n_tmp) 2 { 3 FOR(i,1,n_tmp-1) B[i-1]=1LL*i*A[i]%mod; 4 B[n_tmp-1]=0; 5 return; 6 } 7 inline void Get_jifen(int *A,int *B,int n_tmp) 8 { 9 FOR(i,0,n_tmp-2) B[i+1]=1LL*A[i]*qpow(i+1,mod-2)%mod; 10 B[0]=0; 11 return; 12 } 13 inline void Get_ln(int *A,int *B,int n_tmp) 14 { 15 Get_inv(A,Tmp2,n_tmp); 16 Get_dao(A,Tmp3,n_tmp); 17 Cal_rev(n_tmp); 18 NTT(Tmp2,1),NTT(Tmp3,1); 19 FOR(i,0,lim-1) Tmp2[i]=1LL*Tmp2[i]*Tmp3[i]%mod; 20 NTT(Tmp2,-1); 21 Get_jifen(Tmp2,B,n_tmp); 22 FOR(i,0,lim-1) Tmp2[i]=Tmp3[i]=0; 23 return; 24 }
多项式取指数（exp）
$$B(x) \equiv B_0(x)(1-\ln B_0(x)+A(x))( \mod x^n),其中B_0(x)是模x^{\frac{n}{2}}时的答案$$
1 inline void Get_exp(int *A,int *B,int n_tmp) 2 { 3 if (n_tmp==1) 4 { 5 B[0]=1; 6 return; 7 } 8 int Base=(n_tmp+1)>>1; 9 Get_exp(A,B,Base); 10 FOR(i,Base,n_tmp-1) B[i]=0; 11 Get_ln(B,Tmp1,n_tmp); 12 FOR(i,0,n_tmp-1) Tmp1[i]=((i==0)+A[i]-Tmp1[i]+mod)%mod; 13 FOR(i,0,n_tmp-1) Tmp2[i]=B[i]; 14 Cal_rev(n); 15 NTT(Tmp1,1),NTT(Tmp2,1); 16 FOR(i,0,lim-1) Tmp1[i]=1LL*Tmp1[i]*Tmp2[i]%mod; 17 NTT(Tmp1,-1); 18 FOR(i,0,n_tmp-1) B[i]=Tmp1[i]; 19 FOR(i,0,lim-1) Tmp1[i]=Tmp2[i]=0; 20 return; 21 }
多项式开平方
$$B(x)^2 \equiv A(x) ( \mod x^n)$$
$$B_0(x) \equiv A(x) (\mod x^{\frac{n}{2}})$$
$$(B(x)-B_0(x))^2 \equiv 0 (\mod x^n)$$
$$B^2(x)-2B(x)B_0(x)+B_0^2(x) \equiv (\mod x^n)$$
$$A(x)-2B(x)B_0(x)+B_0^2(x) \equiv (\mod x^n)$$
$$B(x)=\frac{A(x)+B_0^2(x)}{2B_0(x)}$$
多项式开k次方
$$B^k(x)=A(x)$$
$$k\ln B(x)=\ln(A(x))$$
$$B(x)=e^{\frac{\ln A(x)}{k}}$$