题解 有标号无向连通图计数

acwing link。

求 N N N 个节点的无向连通图有多少个，节点有标号，编号为 1 ∼ N 1sim N 1∼N。例如下列图示，三个节点的无向连通图共 4 4 4 个。

设 d p i dp_i dpi​ 表示 i i i 个节点的无向连通图的个数。求连通图个数不好求，考虑求不连通图个数。则 d p i = a l l i − n o t C o n n e c t e d i dp_i=all_i-notConnected_i dpi​=alli​−notConnectedi​。

i i i 个节点的无向图有 C i 2 C_i^2 Ci2​ 条边，每条边可连可不连，所以 a l l i = 2 C i 2 all_i=2^{C_i^2} alli​=2Ci2​。

现在来考虑 n o t C o n n e c t e d i notConnected_i notConnectedi​。首先肯定要枚举什么东西。枚举每条边连不连？那就是 a l l all all 了。枚举断开的两个点？那很难判断连通性。有个好方法：枚举节点 1 1 1 所在连通块大小 j j j。这样既保证了每种情况都能考虑到，也不会重复计算。

首先枚举 j ∈ [ 1 , i ) jin[1,i) j∈[1,i)，对于每个 j j j，节点 1 1 1 所在连通块的节点选择数有 C i − 1 j − 1 C_{i-1}^{j-1} Ci−1j−1​ 种（从 1 1 1 以外 i − 1 i-1 i−1 个节点中取 j − 1 j-1 j−1 个与 1 1 1 在同一个连通块里），而具体边怎么连呢？已经有了答案： d p j dp_j dpj​。剩下的 i − j i-j i−j 个节点怎么连都行了，答案为 a l l i − j all_{i-j} alli−j​。所以能够得出递推式：

d p i = 2 C i 2 − ∑ j = 1 i − 1 C i − 1 j − 1 × d p j × 2 C i − j 2 dp_i=2^{C_i^2}-sumlimits_{j=1}^{i-1}C_{i-1}^{j-1}times dp_jtimes2^{C_{i-j}^2} dpi​=2Ci2​−j=1∑i−1​Ci−1j−1​×dpj​×2Ci−j2​

#include 
using namespace std;

const int N = 9;
long long C[N][N], bit[N*N], dp[N];

void solve(){
	bit[0] = 1; for(int i = 1; i < N*N; ++ i) bit[i] = bit[i-1] * 2;
	for(int i = 0; i < N; ++ i){
		C[i][0] = C[i][i] = 1;
		for(int j = 1; j < i; ++ j) C[i][j] = C[i-1][j-1] + C[i-1][j];
		dp[i] += bit[C[i][2]];
		for(int j = 1; j < i; ++ j)
			dp[i] -= dp[j] * C[i-1][j-1] * bit[C[i-j][2]];
	}
}

但是很快能发现问题：当 n n n 取到 10 10 10 时，就已经爆 long long 了，所以要高精度。

把进位、退位集中在一个函数解决，可以大幅降低写代码的难度。

#include 
using namespace std;

const int N = 52;
struct BigInteger{
	int a[1010], len;
	BigInteger(){ memset(a, 0, sizeof(a)); len = 0; }
	void fix(){
		for(int i = 0; i < len; ++ i){
			if(a[i] < 0) --a[i+1], a[i] += 10;
			a[i+1] += a[i]/10, a[i] %= 10;
		}
		while(a[len] >= 10) a[len+1] += a[len]/10, a[len] %= 10, ++ len;
		while(a[len]) ++ len;
		while(!a[len-1]) -- len;
	}
	void print(){ for(int i = len-1; i >= 0; -- i) putchar(a[i]+'0'); puts(""); }
	void set1(){ a[0] = 1; len = 1; }
	void mul2(){ for(int i = 0; i < len; ++ i) a[i] *= 2; fix(); }
	BigInteger operator + (const BigInteger &y) const {
		BigInteger ans; ans.len = max(len, y.len);
		for(int i = 0; i < ans.len; ++ i) ans.a[i] = a[i] + y.a[i];
		ans.fix(); return ans;
	}
	BigInteger operator - (const BigInteger &y) const {
		BigInteger ans; ans.len = max(len, y.len); 
		for(int i = 0; i < ans.len; ++ i) ans.a[i] = a[i] - y.a[i];
		ans.fix(); return ans;
	}
	BigInteger operator * (const BigInteger &y) const {
		BigInteger ans; ans.len = len + y.len - 1;
		for(int i = 0; i < len; ++ i) for(int j = 0; j < y.len; ++ j) ans.a[i+j] += a[i] * y.a[j];
		ans.fix(); return ans;
	}
} C[N][N], bit[N*N], dp[N];

int main(){
	bit[0].set1(); for(int i = 1; i < N*N; ++ i){ bit[i] = bit[i-1]; bit[i].mul2(); }
	for(int i = 0; i < N; ++ i){
		C[i][0].set1(); C[i][i].set1();
		for(int j = 1; j < i; ++ j) C[i][j] = C[i-1][j-1] + C[i-1][j];
		dp[i] = dp[i] + bit[i*(i-1)/2];
		for(int j = 1; j < i; ++ j)
			dp[i] = dp[i] - dp[j] * C[i-1][j-1] * bit[(i-j)*(i-j-1)/2];
	}
	
 	int n; while(scanf("%d", &n) && n) dp[n].print();
	return 0;
}