题解 Connected Graph

楼教主“男人八题”之首。集训的时候老师讲“简单”DP的时候讲到了这道题，但并没有提及这就是男人八题之一。在凌晨一点一遍A，感觉不是一般的爽(≧∇≦)ﾉ

这道题比较猛，爆搜的复杂度是\(O(2^{\frac {n\times(n-1)}{2}})\),复杂度将以平方的指数级大爆炸，基本上没有写的必要。那就直接讲正解

\[f(n)\quad\quad表示大小为n的标号联通图的个数 \]

\[g(n)\quad\quad表示大小为n的标号不连通图的个数 \]

首先是一个很比较显然的转换公式

\[f(n)=2^{\frac{n\times(n-1)}{2}}-g(n) \]

解释一下：大小为n的标号图的个数为\(2^{\frac{n\times(n-1)}{2}}\),即枚举每一条边的情况。大小为n的标号图必然可以分为联通和不连通两种，因此得到上述转换公式

讲题面要求转换之后，尝试对\(g(n)\)进行求解。

枚举节点 1 所在的联通块大小k，记当前情况为ans。由于 1 处于大小为 k 的联通块中，因此方案数为 f(k) ；又由于图是编号的，因此从除 1 以外的 n-1 个节点中抽 k-1 个节点，作为联通块里的节点，方案数为 C(k-1)(n-1) ；剩下的节点没有任何要求，方案数：\(2^{\frac{(n-k)\times(n-k-1)}{2}}\)；因此总方案数：\(ans=f(k)\times C_{n-1}^{k-1}\times 2^{\frac{(n-k)\times(n-k-1)}{2}}\)

\[g(n)=\sum_{i=1}^{n-1} f(i)\times C_{n-1}^{i-1}\times 2^{\frac{(n-i)\times(n-i-1)}{2}} \]

再结合转化公式，我们即可\(O(n^2)\)求出所有的f(n)φ(゜▽゜*)♪

好了，我们去题面找一找模数就可以开始码题了..找一找..emm..?没有模数？是的，这道题需要手写高精度！而且实测表明，f[50]是一个369位的大数字，再考虑上乘法的进位，实际上我开了1000位(￣▽￣)"

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define lor(a,b,c) for(register int a=b;a<=c;++a)
#define ror(a,b,c) for(register int a=c;a>=b;--a)

struct data{
	static const int MAX=1005;
	int n,num[MAX]; bool nega;

	data(){
		n=0; nega=false; lor(i,0,1000) num[i]=0;
	}

	void print(){
		for(int i=n;i>=1;--i) printf("%d",num[i]);
	}

	void init(string a){
		n=a.length();
		for(int i=n;i>=1;--i) num[i]=a[n-i]-'0';
	}

	void init(int p){
		while(p) {num[++n]=p%10; p/=10;}
	}

	data operator + (data &x){
		data ans;
		ans.n=max(n,x.n);
		lor(i,1,ans.n) ans.num[i]=num[i]+x.num[i];
		lor(i,1,ans.n) ans.num[i+1]+=ans.num[i]/10,ans.num[i]%=10;
		if(ans.num[ans.n+1]) ans.n=ans.n+1;
		return ans;
	}

	data operator - (data &x){
		data ans;
		lor(i,1,n){
			if(num[i]<x.num[i]) num[i+1]--,num[i]+=10;
			ans.num[i]=num[i]-x.num[i];
		}
		ror(i,1,1000) if(ans.num[i]) {ans.n=i; break;}
		return ans;
	}

	data operator * (data &x){
		data ans;
		lor(i,1,n) lor(j,1,x.n) ans.num[i+j-1]+=num[i]*x.num[j];
		lor(i,1,n+x.n) ans.num[i+1]+=ans.num[i]/10,ans.num[i]%=10;
		ror(i,0,1000) if(ans.num[i]) {ans.n=i; break;}
		return ans;
	}

	data operator * (int tim){
		data ans;
		lor(i,1,n) ans.num[i]=num[i]*tim;
		lor(i,1,n+10) ans.num[i+1]+=ans.num[i]/10,ans.num[i]%=10;
		ror(i,0,1000) if(ans.num[i]) {ans.n=i; break;}
		return ans;
	}

	data operator / (int div){
		data ans;
		int rec=0;
		ror(i,1,n){
			rec=(rec<<1)+(rec<<3)+num[i];
			while(rec>=div) ans.num[i]++,rec-=div;
		}
		ror(i,1,1000) if(ans.num[i]) {ans.n=i; break;}
		return ans;
	}
};
typedef data gjd;

const int MAX=55;

int n;
gjd n1,n2,n3,n4,c[MAX][MAX],f[MAX],g[MAX];

inline int read();
void init();
gjd qsm(int,int);

int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	#endif

	init();

	while(n=read(),n){
		f[n].print(); printf("\n");
	}
	

	return 0;
}

inline int read(){
	char tmp=getchar(); int sum=0; bool flag=false;
	while(tmp<'0'||tmp>'9'){
		if(tmp=='-') flag=true;
		tmp=getchar();
	}
	while(tmp>='0'&&tmp<='9'){
		sum=(sum<<1)+(sum<<3)+tmp-'0';
		tmp=getchar();
	}
	return flag?-sum:sum;
}

void init(){
	c[0][0].init("1");
	lor(i,1,50) c[i][0].init("1"),c[i][i].init("1");
	lor(i,2,50) lor(j,1,i-1) c[i][j]=c[i-1][j-1]+c[i-1][j];

	lor(i,1,50){
		lor(j,1,i-1){
			gjd tmp=qsm(2,(i-j)*(i-j-1)/2)*f[j]*c[i-1][j-1];
			g[i]=g[i]+tmp;

		}
		f[i]=qsm(2,(i)*(i-1)/2)-g[i];
	}
}

gjd qsm(int base,int k){
	data ans,skip;
	ans.init(1); skip.init(base);
	while(k){
		if(k&1) ans=ans*skip;
		skip=skip*skip;
		k>>=1;
	}
	return ans;
}