BZOJ3456:城市規劃(EGF FFT/CDQ分治 FFT)

NO IMAGE

傳送門

題意:無向連通圖的計數。

題解:
首先一個簡單無向圖由若干簡單連通圖拼接而成。

一個簡單無向圖的指數級生成函式為:

G(x)=∑i=1∞2(i2)xii!

G(x)=\sum_{i=1}^{\infty}2^{\binom{i}{2}}\frac{x^i}{i!}

設一個簡單連通圖的指數級生成函式為:

F(x)=∑i=1nCnxii!

F(x)=\sum_{i=1}^{n}C_n\frac{x^i}{i!}

那麼可以推匯出:

G(x)=∑i=0∞(F(x))ii!

G(x)=\sum_{i=0}^{\infty}\frac{(F(x))^i}{i!}

相當於由若干簡單連通圖生成了一個簡單無向圖,ii個簡單連通圖拼接會多算i!i!次。

由泰勒展開可得:

G(x)=eF(x)

G(x)=e^{F(x)}

進一步地,有:

F(x)=lnG(x)

F(x)=\ln G(x)
對兩邊同時求導,得:

F′(x)=G′(x)G(x)

F'(x)=\frac{G'(x)}{G(x)}

把這個式子放在mod(n 1)\mod (n 1)意義下計算即可。

#include<bits/stdc  .h>
using namespace std;
const int Mod=1004535809;
const int G=3,Maxn=5e5 50;
inline int power(int a,int b){
    int rs=1;
    for(;b;b>>=1,a=1ll*a*a%Mod)if(b&1)rs=1ll*rs*a%Mod;
    return rs;
}
int tp[Maxn],tp2[Maxn];
struct FFT{
    int pw[Maxn],pos[Maxn],k;
    inline void dft(int *A,int len){
        pw[0]=1;int tt=power(G,(Mod-1)/len);
        for(int i=1;i<len;i  )pw[i]=1ll*pw[i-1]*tt%Mod;
        for(int i=1;i<len;i  )pos[i]=(i&1)?((pos[i>>1]>>1)^(len>>1)):(pos[i>>1]>>1);
        for(int i=1;i<len;i  )if(pos[i]>i)swap(A[pos[i]],A[i]);
        for(int bl=1;bl<len;bl<<=1){
            int tl=bl<<1,ct=len/tl,wn=pw[ct];
            for(int p=0;p<len;p =tl){
                int w=1;
                for(int j=0;j<bl;j  ){
                    int &a=A[p j],&b=A[p j bl],t=1ll*b*w%Mod;
                    b=(a-t Mod)%Mod;
                    a=(a t)%Mod;
                    w=1ll*w*wn%Mod;
                }
            }
        }
    }
    inline void calc_inv(int *A,int *B,int len){
        if(len==1){
            B[0]=power(A[0],Mod-2);
            return;
        }
        if(len!=1)calc_inv(A,B,len>>1);
        memcpy(tp,B,sizeof(int)*len);
        memcpy(tp2,A,sizeof(int)*len);
        int t=len<<1;
        dft(tp,t);dft(tp2,t);
        for(int i=0;i<t;i  ){
            tp[i]=2ll*tp[i]%Mod-1ll*tp[i]*tp[i]%Mod*tp2[i]%Mod;
            tp[i] =(tp[i]<0?Mod:0);
        }
        dft(tp,t);
        int rv=power(t,Mod-2);
        reverse(tp 1,tp t);
        for(int i=0;i<len;i  ){
            B[i]=1ll*tp[i]*rv%Mod;
        }
    }
}fft;
int n,A[Maxn],A_df[Maxn],inv_A[Maxn],fac[Maxn]; 
int main(){
    scanf("%d",&n);
    A[0]=A[1]=1;A_df[0]=1;
    fac[0]=1;
    for(int i=1;i<=n;i  )fac[i]=fac[i-1]*1ll*i%Mod;
    for(int i=2;i<=n;i  ){
        A[i]=1ll*power(2,(1ll*i*(i-1)/2)%(Mod-1))%Mod;
        A[i]=1ll*A[i]*power(fac[i],Mod-2)%Mod;
        A_df[i-1]=1ll*A[i]*i%Mod;
    }
    int t=1;while(t<n)t<<=1;
    t<<=1;int tot=0;
    fft.calc_inv(A,inv_A,t/2);
    for(int i=0;i<n;i  ){
        tot =1ll*A_df[i]*inv_A[n-i-1]%Mod;
        tot-=(tot>Mod?Mod:0);
    }
    cout<<(1ll*tot*fac[n-1])%Mod<<endl;
}

當然,分治加FFT也是很支援的。具體可以看網上的推導

#include<bits/stdc  .h>
using namespace std;
const int Mod=1004535809;
const int G=3;
const int N=5e5 50;
inline int power(int a,int b){
    int rs=1;
    for(;b;b>>=1,a=1ll*a*a%Mod)
        if(b&1)rs=1ll*rs*a%Mod;
    return rs;
}
struct fft{
    int k,pos[N],w[N];
    inline void pre(int len){
        for(k=1;k<len;k<<=1);
        k<<=1;w[0]=1;
        int wn=power(G,(Mod-1)/k);
        for(int i=1;i<k;i  )w[i]=1ll*w[i-1]*wn%Mod;
        for(int i=1;i<k;i  )pos[i]=(pos[i>>1]>>1)|((i&1)?k>>1:0);
    }
    inline void dft(int *a){
        for(int i=1;i<k;i  )if(i>pos[i])swap(a[i],a[pos[i]]);
        for(int bl=1;bl<k;bl<<=1){
            int tl=bl<<1,wn=w[k/tl];
            for(int bg=0;bg<k;bg =tl){
                int ws=1;
                for(int j=0;j<bl;  j){
                    int &A=a[bg j],&B=a[bg j bl],t=1ll*B*ws%Mod;
                    B=(A-t Mod)%Mod;
                    A=(A t)%Mod;
                    ws=1ll*ws*wn%Mod;
                }
            }
        }
    }
    inline void mul(int *a,int *b,int *c){
        dft(a);dft(b);
        for(int i=0;i<k;i  )c[i]=1ll*a[i]*b[i]%Mod;
        dft(c);reverse(c 1,c k);
        int rv=power(k,Mod-2);
        for(int i=0;i<k;i  )c[i]=1ll*c[i]*rv%Mod;
    }
}fft;
int n,pw[N],fac[N],inv_fac[N],a[N],b[N],f[N];
inline void solve(int l,int r){
    if(l==r){f[l]=(pw[l]-1ll*f[l]*fac[l-1]%Mod Mod)%Mod;return;}
    int mid=(l r)>>1;
    solve(l,mid);
    int len=r-l 1;fft.pre(len);
    a[0]=0;b[0]=0;
    for(int i=l;i<=mid;i  )a[i-l 1]=1ll*f[i]*inv_fac[i-1]%Mod;
    for(int i=1;i<=len;i  )b[i]=1ll*pw[i]*inv_fac[i]%Mod;
    for(int i=mid-l 2;i<=fft.k;i  )a[i]=0;
    for(int i=len 1;i<=fft.k;i  )b[i]=0;
    fft.mul(a,b,a);
    for(int i=mid 1;i<=r;i  )f[i]=(f[i] a[i-l 1])%Mod;
    solve(mid 1,r);
}
int main(){
    scanf("%d",&n);
    int len=1;
    while(len<n)len<<=1;
    len<<=1;pw[0]=1;fac[0]=(inv_fac[0]=1);
    for(int i=1;i<=len;i  )pw[i]=power(2,(1ll*i*(i-1)/2)%(Mod-1));
    for(int i=1;i<=len;i  )fac[i]=1ll*fac[i-1]*i%Mod;
    for(int i=1;i<=len;i  )inv_fac[i]=power(fac[i],Mod-2);
    solve(1,n);
    cout<<f[n]<<endl;
}