【FZYZOJ】无向图的联通图个数题解（组合数学）

题目大意：求无向图的连通图个数。由于个数可能很大，只需要求出结果$mod1000000009$的值。$n\leq 1000$

-------------------------

对于一个含有$n$个结点的图，一共有$2^{\frac{n(n-1)}{2}}$种情况（把所有边连或不连都考虑到了，可以自行模拟出来）我们假设$h[n]=2^{\frac{n(n-1)}{2}}$。设$f[n]$表示大小为$n$的图的无向连通图个数。接下来我们假设图中有一个点$1$（叫什么都行）。

假设这个点只与$i-1$个点相连了。那么它们组成了一个大小为$i$的子图，方案数为$f[i]$。挑选方式有$C(n-1,i-1)$种。剩下还有$n-i$个点没有与这个子图联通，而它们之间的联通情况是随意的，即$h[n-i]$种。所以此时整个图不连通的情况有$C(n-1,i-1)*f[i]*h[n-i]$种。

因为$i$可以从$1$枚举到$n-1$，所以总的表达式有：

$h[n]=2^{\frac{n(n-1)}{2}}$

$f[n]=h[n]-\sum_{i=1}^{n-1} C(n-1,i-1)*f[i]*h[n-i]$

转移是$O(n)$的，快速幂$logn$。预处理$n^2$。

代码：

#include<bits/stdc++.h>

using namespace std;

const long long p=1e9+;

long long f[],h[],C[][];

int n;

inline int qpow(int a,int b) { register long long ret=; a%=p;

    for(;b;b>>=,a=(long long)a*a%p) if(b&) ret=ret*a%p; return ret;

}

int main()

{

    cin>>n;

    for (int i=;i<=n;i++)

    {

        C[i][]=;

        for (int j=;j<=i;j++) C[i][j]=(long long)(C[i-][j-]+C[i-][j])%p;

    }

    for (int i=;i<=n;i++) h[i]=qpow(,i*(i-)/);

    for (int i=;i<=n;i++)

    {

        f[i]=h[i];

        for (int j=;j<i;j++) f[i]=(f[i]-(long long)C[i-][j-]*f[j]%p*h[i-j]%p+p)%p;

        f[i]=(f[i]+p)%p;

    }

    printf("%lld",f[n]);

    return ;

}

巴特西

【FZYZOJ】无向图的联通图个数题解（组合数学）

最新文章

热门文章

巴特西

【FZYZOJ】无向图的联通图个数 题解（组合数学）

最新文章

热门文章

【FZYZOJ】无向图的联通图个数题解（组合数学）