zcmimi's blog
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

#include<bits/stdc++.h>
const int N=1<<18,P=1004535809;
typedef long long ll;
int n;
void mod(int&x){if(x>=P)x-=P;}
template<class T>
int pw(int x,T b){
    int res=1;
    for(;b;b>>=1,x=1ll*x*x%P)
        if(b&1)res=1ll*res*x%P;
    return res;
}

int inv(int x){return pw(x,P-2);}
int L,r[N];
void getL(int n){
    for(L=1;L<n;L<<=1);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
void swap(int&x,int&y){int t=x;x=y;y=t;}
const int G=3,Gi=inv(G);
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1)
            for(int k=0,w=1;k<len;++k,w=1ll*w*Wn%P){
                int t=1ll*w*A[i+k+len]%P;
                mod(A[i+k+len]=A[i+k]-t+P);
                mod(A[i+k]+=t);
            }
    }
    if(~typ)return;
    for(int i=0,il=inv(L);i<L;++i)A[i]=1ll*A[i]*il%P;
}
void mul(int*A,int*B,int*C,int n){
    static int a[N],b[N];
    getL(n<<1);
    memcpy(a,A,n*4),memcpy(b,B,n*4);
    memset(a+n,0,(L-n)*4),memset(b+n,0,(L-n)*4);
    ntt(a,1),ntt(b,1);
    for(int i=0;i<L;++i)C[i]=1ll*a[i]*b[i]%P;
    ntt(C,-1);
    memset(C+n,0,(L-n)*4);
}
void inv(int*A,int*B,int n){
    if(n==1)return B[0]=inv(A[0]),void();
    inv(A,B,(n+1)>>1);
    getL(n<<1);
    static int C[N];
    memcpy(C,A,n*4);memset(C+n,0,(L-n)*4);
    ntt(B,1);ntt(C,1);
    for(int i=0;i<L;++i)
        B[i]=1ll*B[i]*(2-1ll*B[i]*C[i]%P+P)%P;
    ntt(B,-1);
    memset(B+n,0,(L-n)*4);
}
void dvt(int*A,int*B,int n){
    for(int i=1;i<n;++i)
        B[i-1]=1ll*i*A[i]%P;
    B[n-1]=0;
}
void itr(int*A,int*B,int n){
    for(int i=1;i<n;++i)
        B[i]=1ll*inv(i)*A[i-1]%P;
    B[0]=0;
}
void ln(int*A,int*B,int n){
    static int a[N],b[N],B_[N];
    memset(b,0,n*4);
    dvt(A,a,n),inv(A,b,n);
    mul(a,b,B_,n);
    itr(B_,B,n);
}
int main(){
    scanf("%d",&n);++n;
    static int g[N],f[N],fac[N];
    getL(n);
    fac[0]=1;
    for(int i=1;i<n;++i)fac[i]=1ll*fac[i-1]*i%P;
    g[0]=1;
    for(int i=1;i<n;++i)g[i]=1ll*pw(2,1ll*i*(i-1)/2%(P-1))*inv(fac[i])%P;
    ln(g,f,n);
    printf("%d\n",1ll*f[n-1]*fac[n-1]%P);
}
LG 4841 [集训队作业2013]城市规划
comment评论
Search
search