多项式模板整理

多项式乘法

 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 }

View Code

多项式求逆

$$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-2B'+AB'^2equiv0( mod x^n)$$

$$Bequiv B'(2-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 }

View Code

多项式取对数（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 }

View Code

多项式取指数（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 }

View Code

多项式开平方

$$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)$$

$$kln B(x)=ln(A(x))$$

$$B(x)=e^{frac{ln A(x)}{k}}$$