题解：P10982 Connected Graph

Mirasycle · 2025-06-24 00:35:00 · 题解

图计数入门题。

记 e_i 表示 i 个的完全图的边数 {i\choose 2}，设 f_i 表示 i 个点的标号联通图。

考虑使用容斥，先 f_i\gets 2^{e_i}，然后再扣除不合法的方案数。不合法的方案必定是需要不联通的，不联通图可以被划分为至少两个内部联通点集（集合之间不联通），如果直接枚举的话不好确定对象，不妨把只枚举其中一个内部联通且和外部不联通的集合，这个集合确定之后，我们可以发现外面是可以任意选择的，不管外面怎么选，都能被划分为至少两个之间不联通的点集。

但是我们钦定的这个联通的点集，会在一个拥有多个联通块的图中被计算多次（每个联通块可以作为被钦定联通的集合），发现这张图中 1 号点所在联通块唯一，于是我们就强行要求包含 1 号点所有在联通块这样子就唯一了。

我们直接枚举被钦定联通的集合大小，然后组合数是分配系数，由于 1 号点已经被要求在集合中了，所有只需要从剩下的 i-1 个点中选择 j-1 个就行了。最后 2^{e_{i-j}} 代表剩余部分随便选的方案数。

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
const int mod=1004535809;
void add(int &x,int y){ x=x+y>=mod?x+y-mod:x+y; }
void sub(int &x,int y){ x=x<y?x-y+mod:x-y; }
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int f[maxn],pw[maxn*maxn],C[maxn][maxn],n;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; C[0][0]=1; pw[0]=1;
    for(int i=1;i<=n*n;i++) pw[i]=2ll*pw[i-1]%mod;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=pw[C[i][2]];
        for(int j=1;j<i;j++)
            sub(f[i],1ll*f[j]*C[i-1][j-1]%mod*pw[C[i-j][2]]%mod);
    }
    cout<<f[n];
    return 0;
}