图论--连通图计数模板

问题：含有n个不同的点的连通图有多少种，即同构的图算是多个。

记　含有n个点的连通图个数为 F[n] ；

　　含有n个点的不连通图个数为 G[n] ；

　　含有n个点的图的个数为 H[n] = 2^(n*(n-1)/2) ；

　　有  F[n] + G[n] = H[n] ；　　F[n] = H[n] - G[n] ；

因此要求 F[n] 只需求 G[n] ；

求 G[n] ：枚举 1 号点所在的连通块大小为 k ( 1 ~ n-1 ) ；

　　　　　当 1 号点所在连通块大小为 k 时： k个点选取情况为组合数  C[n-1][k-1]

　　　　　　　　　　　　　　　　　　　　　该连通块的种类数确定 k 个点后，连通块的种类数为 F[k] 

　　　　　　　　　　　　　　　　　　　　　剩余 n-k 个点组成的图的种类数 H[n-k]

　　　　　　　　　　　　　　　　　　　　　因此情况数为 C[n-1][k-1] * F[k] * H[n-k]

　　　　　G[n]为所有枚举的情况数总和  Σ( k : 1 ~ n-1 ) ( C[n-1][k-1] * F[k] * H[n-k] )

定初始值 F[1] = 1 , G[1] = 1

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;

const int maxn=1e3+5;
const int mod=1e9+7;

ll C[maxn][maxn];        //组合数
ll F[maxn],G[maxn],H[maxn];

ll QP(ll a,ll n){        //快速幂
    ll tmp=a,ans=1;
    while(n){
        if(n&1)ans=ans*tmp%mod;
        tmp=tmp*tmp%mod;
        n>>=1;
    }
    return ans;
}

void init(){
    for(int i=1;i<maxn;++i)H[i]=QP(2,i*(ll)(i-1)/2);
    for(int i=0;i<maxn;++i){
        for(int j=0;j<=i;++j){
            C[i][j]=(i&&j)?(C[i-1][j]+C[i-1][j-1])%mod:1;
        }
    }
    F[1]=1;G[1]=1;
    for(int i=2;i<maxn;++i){
        G[i]=0;
        for(int k=1;k<i;++k){
            G[i]=(G[i]+C[i-1][k-1]*F[k]%mod*H[i-k]%mod)%mod;
        }
        F[i]=((H[i]-G[i])%mod+mod)%mod;
    }
}