题解：P10982 Connected Graph

图计数入门题。

记

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}}

代表剩余部分随便选的方案数。

f_i=2^{e_i}-\sum\limits_{j=1}^{i-1}f_j\times {i-1\choose j-1}\times 2^{e_{i-j}}

时间复杂度

O(n^2)

。

CPP

#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;
}

题解：P10982 Connected Graph

文章操作

相关推荐

评论

题解：P10982 Connected Graph