Description
An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v. You are to write a program that tries to calculate the number of different connected undirected graph with n vertices. For example,there are 4 different connected undirected graphs with 3 vertices.
Input
The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.
Output
For each test case output the answer on a single line.
Sample Input
1 2 3 4 0Sample Output
1 1 4 38
题意：
求N个点的无向连通图有多少个。
解析：
计数类DP。
N个点的无向图总数显然为（乘法原理）。
考虑用总数减去不连通数，一张不连通的无向图必定由若干个连通块构成。我们可以枚举标号为1的节点所在连通块包含节点的个数 K，从 2~N 这 N-1 个节点中选出 K-1 个节点构成任意无向图，有种选法。
综上，令表示 i 个节点的无向连通图的个数，于是就有以下状态转移方程：
还是容易理解的。
PS：这题要用高精就真的恶心了。。。
代码：
//created by lyd #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; int n; struct H {int a[400],len;}f[60],power[60]; inline H operator / (const H &x,const int y) { H z; memset(z.a,0,sizeof z.a); z.len=0; int left=0; for(int i=x.len;i>=1;i--) { left=left*10+x.a[i]; z.a[i]=left/y; left%=y; if(!z.len&&z.a[i]) z.len=i; } return z; } inline H operator + (const H &x,const H &y) { H z; memset(z.a,0,sizeof z.a); for(int i=1;i<=max(x.len,y.len);i++) { z.a[i]+=x.a[i]+y.a[i]; z.a[i+1]=z.a[i]/10; z.a[i]%=10; } z.len=max(x.len,y.len); if(z.a[z.len+1]) z.len++; return z; } inline H operator * (const H &x,const H &y) { H z; memset(z.a,0,sizeof z.a); for(int i=1;i<=x.len;i++) for(int j=1;j<=y.len;j++) { z.a[i+j-1]+=x.a[i]*y.a[j]; z.a[i+j]+=z.a[i+j-1]/10; z.a[i+j-1]%=10; } z.len=x.len+y.len-1; if(z.a[z.len+1]) z.len++; return z; } inline H C(int x,int y) { H tot,temp; tot.len=1; tot.a[1]=1; for(int i=y,j=1;j<=x;i--,j++) { int t=i; temp.len=0; while(t) { temp.a[++temp.len]=t%10; t/=10; } tot=tot*temp/j; } return tot; } inline void print(const H &x) { for(int i=x.len;i>=1;i--) printf("%d",x.a[i]); printf("\n"); } int main() { for(int i=1;i<=50;i++) { long long temp=((long long)(1)<<i)-1; while(temp) { power[i].a[++power[i].len]=temp%10; temp/=10; } } f[1].len=1;f[1].a[1]=1; f[2].len=1;f[2].a[1]=1; for(int i=3;i<=50;i++) for(int j=1;j<=i-1;j++) f[i]=f[i]+C(j-1,i-2)*f[j]*f[i-j]*power[j]; while(scanf("%d",&n),n) print(f[n]); return 0; }
