POJ1737 Connected Graph 高精度+递推

题意:求出\(n\)个点的无向完全图的子图中有多少个是连通图.

思路:

令\(f_i\)表示\(i\)个点时的连通图个数.

考虑如果图不连通,那么必定存在某些点与\(1\)号点不在一个连通分量中.

如果我们要计算\(f_n\),那就枚举和\(1\)号点在一个连通分量中中的有几个点,那么与这个连通分量无关的点的集合内部就可以随便连边了.这种情况下我们要考虑是哪些点和\(1\)号点在一个连通分量中,另外还要乘上这个连通分量的内部连边数.这个是之前已经搞出来的.

随后利用高精度预处理一下直接输出.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

static const int mod=1e4;
struct Int{
	int d[500],l;
	Int():l(1){memset(d,0,sizeof d);}
	inline void operator=(const int&x){memset(d,0,sizeof d),l=1,d[0]=x;}
	inline void operator+=(const Int&B){
		l=l>B.l?l:B.l;for(int i=0;i<l;++i)if((d[i]+=B.d[i])>=mod)d[i]-=mod,d[i+1]++;
		if(d[l])l++;
	}
	inline void operator*=(const Int&B){
		Int C;
		for(int i=0;i<l;++i)for(int j=0;j<B.l;++j){
			C.d[i+j]+=d[i]*B.d[j];if(C.d[i+j]>=mod)C.d[i+j+1]+=C.d[i+j]/mod,C.d[i+j]%=mod;
		}
		for(C.l=l+B.l+1;!C.d[C.l-1];--C.l);
		*this=C;
	}
	inline void operator-=(const Int&B){
		for(int i=0;i<B.l;++i){if((d[i]-=B.d[i])<0){d[i]+=mod,d[i+1]--;}}
		while(l>1&&d[l-1]==0)--l;
	}
	Int operator*(const Int&B)const{Int r=*this;r*=B;return r;}
	inline void print(){
		printf("%d",d[l-1]);for(int i=l-2;i>=0;--i)printf("%04d",d[i]);
	}
};
Int pow(int y){
	Int t,r;for(t=2,r=1;y;y>>=1,t*=t)if(y&1)r*=t;return r;
}
Int C[51][51];
inline void Init(){
	C[0][0]=1,C[1][0]=1,C[1][1]=1;
	for(int i=2;i<=50;++i){
		C[i][0]=1,C[i][i]=1;
		for(int j=1;j<i;++j)C[i][j]=C[i-1][j-1],C[i][j]+=C[i-1][j];
	}
}
Int f[51];

int main(){
	f[1]=1;Init();
	for(int i=2;i<=50;++i){
		f[i]=pow(i*(i-1)>>1);
		for(int j=0;j<i-1;++j)f[i]-=C[i-1][j]*f[j+1]*pow((i-j-1)*(i-j-2)>>1);
	}
	int x;while(scanf("%d",&x)&&x)f[x].print(),puts("");
	return 0;
}