多项式求ln,求exp,开方,快速幂学习总结-白红宇

多项式求ln,求exp,开方,快速幂学习总结

阅读量：4947 次

发布时间：2019-06-11

本文共 7017 字，大约阅读时间需要 23 分钟。

按理说Po姐姐三月份来讲课的时候我就应该学了

但是当时觉得比较难加上自己比较懒，所以就QAQ了

现在不得不重新弄一遍了

首先说多项式求ln

设G(x)=lnF(x)

我们两边求导可以得到G'(x)=F‘(x)/F(x)

则G(x)就是F’(x)/F(x)的积分

我们知道多项式求导和积分是O(n)的,多项式求逆是O(nlogn)的

所以总时间复杂度O(nlogn)

多项式求ln一般解决的问题是这样的

设多项式f表示一些奇怪的东西，由一些奇怪的东西有序组成的方案为

f^1+f^2+f^3…… 化简之后得到多项式求逆的式子

而由这些奇怪的东西无序组成的方案为

f^1/1!+f^2/2！……

由泰勒展开我们知道化简后为e^f

则若我们知道e^f,求f就需要多项式求ln了

这样推导非常的优美

譬如说BZOJ 3456 城市规划

设答案为多项式f，设n个点的无向图个数为多项式g

不难发现无向图是由若干个无序联通块组成的

我们得到式子g=e^f

而多项式g是非常好构造的，f=ln(g)

多项式求ln即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define G 3using namespace std; typedef long long LL;const int maxn=300010;const int mod=1004535809;int n,N,len,rev[maxn];int jc[maxn],inv[maxn];int g[maxn],f[maxn],w[maxn]; int pow_mod(int v,int p){    int tmp=1;    while(p){        if(p&1)tmp=1LL*tmp*v%mod;        v=1LL*v*v%mod;p>>=1;    }return tmp;}void FFT(int *A,int n,int flag){    for(int i=0;i
          
           
            >1); int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k); w[0]=1; for(int i=1;i
            
             >1); int now=(n<<1); for(len=0;(1<
             
              
               >1]>>1|((i&1)<<(len-1)); static int tmp[maxn]; for(int i=0;i
               
                =0;--i)f[i]=1LL*f[i-1]*pow_mod(i,mod-2)%mod;} int main(){ scanf("%d",&n); for(N=1;N<=n;N<<=1); jc[0]=1; for(int i=1;i
                
                 =0;--i)inv[i]=1LL*inv[i+1]*(i+1)%mod; for(int i=0;i
                 
                  >1]>>1|((i&1)<<(len-1)); FFT(g,N,1);FFT(f,N,1); for(int i=0;i

cojs 2358

首先用多项式求逆可以搞出n个点的DAG的个数，这个不再多说

我们不难发现n个点的DAG是由若干个DAG的弱连通图无序组成的

多项式求ln即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define G 3using namespace std;const int maxn=300010;const int mod=998244353;int n,N,len,w[maxn];int jc[maxn],inv[maxn],rev[maxn];int f[maxn],Inv[maxn],ln[maxn];int pow_mod(int v,int p){	int tmp=1;	while(p){		if(p&1)tmp=1LL*tmp*v%mod;		v=1LL*v*v%mod;p>>=1;	}return tmp;}void FFT(int *A,int n,int flag){	for(int i=0;i
          
           
            >1); int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k); w[0]=1; for(int i=1;i
            
             =1;--i)ln[i]=1LL*ln[i-1]*pow_mod(i,mod-2)%mod; ln[0]=0;}void Get_inv(int n){ if(n==1){ Inv[0]=pow_mod(f[0],mod-2); return; } Get_inv(n>>1); int now=(n<<1); for(len=0;(1<
             
              
               >1]>>1|((i&1)<<(len-1)); static int tmp[maxn]; for(int i=0;i
               
                >1]>>1|((i&1)<<(len-1)); FFT(Inv,now,1);FFT(f,now,1); for(int i=0;i
                
                 =0;--i)inv[i]=1LL*inv[i+1]*(i+1)%mod; for(int i=0;i
                 
                  >1,tmp)*inv[i]%mod; if(i&1)f[i]=mod-f[i]; }Get_inv(N); for(int i=0;i<=n;++i){ int tmp=(1LL*i*(i-1)/2)%(mod-1); f[i]=1LL*Inv[i]*pow_mod(2,tmp)%mod*jc[i]%mod; f[i]=1LL*f[i]*inv[i]%mod; } for(int i=n+1;i

多项式求exp

用处其实跟多项式求ln是相反的

对于式子g=e^f，假设我们知道f，求g就需要用到多项式求exp了

多项式求exp的方式是利用牛顿迭代法倍增

设F(x)=e^A(x)

我们知道若G(F0(x))=0(mod x^n)

我们有G(F(x))=0=G(F0(x))/0!+G‘(F0(x))/1!*(F(x)-F0(x))(mod x^2n)

转换一下式子我们可以得到F(x)的表达式

我们又知道G(F(x))=lnF(x)-A(x)

带入上面的式子整理之后我们得到F(x)=F0(x)*(1-lnF0(x)+A(x))

无脑倍增就可以了,每次倍增的时候求ln即可，常数巨大，但还是O(nlogn)的

本来应该出到cojs的题目QAQ但是因为自己的权限掉了QAQ

求前n项的Bell数

在之前的文章里提到了Bell数可以利用CDQ+FFT解决

但是我们也提到了Bell数的生成函数e^(e^x-1)

我们对e^x-1做泰勒展开，之后多项式求exp即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define G 3using namespace std;const int mod=998244353;const int maxn=300010;int n,N,len,T;int jc[maxn],inv[maxn],rev[maxn],w[maxn];int g[maxn],f[maxn],h[maxn],ni[maxn];int Exp[maxn],ln[maxn],Inv[maxn];int C[maxn];struct ASK{	int n;}Q[maxn];int pow_mod(int v,int p){	int tmp=1;	while(p){		if(p&1)tmp=1LL*tmp*v%mod;		v=1LL*v*v%mod;p>>=1;	}return tmp;}void FFT(int *A,int n,int flag){	for(int i=0;i
          
           
            >1); int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k); w[0]=1; for(int i=1;i
            
             =1;--i)ln[i]=1LL*ln[i-1]*ni[i]%mod; ln[0]=0;}void Get_inv(int n){ if(n==1){ Inv[0]=pow_mod(f[0],mod-2); return; } Get_inv(n>>1); int now=(n<<1); for(len=0;(1<
             
              
               >1]>>1|((i&1)<<(len-1)); static int tmp[maxn]; for(int i=0;i
               
                >1]>>1|((i&1)<<(len-1)); FFT(Inv,now,1);FFT(f,now,1); for(int i=0;i
                
                 >1); int now=(n<<1); for(int i=0;i
                 
                  >1]>>1|((i&1)<<(len-1)); FFT(Exp,now,1);FFT(ln,now,1); for(int i=0;i
                  
                   =0;--i)inv[i]=1LL*inv[i+1]*(i+1)%mod; for(int i=2;i

多项式开根

同样是利用倍增

设G^2(x)=F(x)(mod x^n)

我们得到(G^2(x)-F(x))^2=0(mod x^2n)

又可以得到(G^2(x)+F(x))^2=4*G^2(x)*F(x)(mod x^2n)

即((G^2(x)+F(x))/2*G(x))^2=F(x)(mod x^2n)

显然括号里面的东西是我们要求的东西，求解即可

注意到多项式开根的前提是常数项可开根，但如果在模意义下并不要求常数项是完全平方数

只要常数项存在二次剩余就可以了，至于求解的话可以利用原根的性质求解

BZOJ 3625

我们设答案多项式为F(x)

我们得到生成函数F(x)=C(x)F^2(x)+1

得到C(x)F^2(x)-F(x)+1=0

F(x)=(1 +or- sqrt(1-4C(x))/2C(x))=2/(1 +or- sqrt(1-4C(x)))

由于多项式求逆要求常数项存在逆，所以可以确定是加号

之后做多项式开根之后多项式求逆即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define G 3using namespace std; const int maxn=300010;const int mod=998244353;int n,m,x,N,len,C;int f[maxn],rt[maxn],Inv[maxn],rev[maxn];int w[maxn]; void read(int &num){    num=0;char ch=getchar();    while(ch<'!')ch=getchar();    while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();}int pow_mod(int v,int p){    int tmp=1;    while(p){        if(p&1)tmp=1LL*tmp*v%mod;        v=1LL*v*v%mod;p>>=1;    }return tmp;}void FFT(int *A,int n,int flag){    for(int i=0;i
          
           
            >1); int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k); w[0]=1; for(int i=1;i
            
             >1); int now=(n<<1); for(len=0;(1<
             
              
               >1]>>1|((i&1)<<(len-1)); static int tmp[maxn]; for(int i=0;i
               
                >1); for(int i=0;i
                
                 >1]>>1|((i&1)<<(len-1)); FFT(Inv,now,1);FFT(tmp,now,1); for(int i=0;i
                 
                  >1); for(N=1;N<=m;N<<=1); for(int i=1;i<=n;++i){ read(x); if(x<=m)f[x]++; } for(int i=0;i

多项式快速幂

即求F^k(x)

我们可以直接做快速幂每次乘完消掉次数界既可以了

但是这样的做法不够高大上

我们知道F^k(x)=exp(ln(F^k(x))

而ln(F^k(x))=k*ln(F(x))

我们做多项式求ln，然后系数乘以k之后exp还原即可

时间复杂度O(nlogn)

多项式的学习估计就到此结束啦，以后可能会学一些用FFT优化DP，用FFT优化字符串匹配的题目

当然也会写总结啦

听说多项式还有什么多点插值，扩展欧几里得，拉格朗日反演之类的鬼东西

先暂时弃掉咯

最后附上多项式终极模板，也是zcg他们出的毒瘤题目

cojs 2189 帕秋莉的超级多项式

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define G 3using namespace std;const int maxn=300010;const int mod=998244353;int n,k,N,C,len;int rev[maxn],w[maxn];int f[maxn],rt[maxn];int Inv[maxn],ln[maxn],Exp[maxn];int pow_mod(int v,int p){ int tmp=1; while(p){ if(p&1)tmp=1LL*tmp*v%mod; v=1LL*v*v%mod;p>>=1; }return tmp;}void FFT(int *A,int n,int flag){ for(int i=0;i
           
            
             >1); int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k); w[0]=1; for(int i=1;i
             
              =1;--i)f[i]=1LL*f[i-1]*pow_mod(i,mod-2)%mod; f[0]=0;}void Get_dao(int *f,int n){ f[n]=0; for(int i=0;i
              
               >1,h); int now=(n<<1); static int tmp[maxn]; for(int i=0;i
               
                >1]>>1|((i&1)<<(len-1)); FFT(tmp,now,1);FFT(Inv,now,1); for(int i=0;i
                
                 >1); int now=(n<<1); for(int i=0;i
                 
                  >1]>>1|((i&1)<<(len-1)); FFT(tmp,now,1);FFT(Inv,now,1); for(int i=0;i
                  
                   >1]>>1|((i&1)<<(len-1)); FFT(h,now,1);FFT(Inv,now,1); for(int i=0;i
                   
                    >1); int now=(n<<1); static int g[maxn]; for(int i=0;i
                    
                     >1]>>1|((i&1)<<(len-1)); FFT(ln,now,1);FFT(Exp,now,1); for(int i=0;i
                     
                      >1); for(int i=0;i