题目描述： LTC不知道是谁？百度去！楼天成是也，楼教主当年提出来的男人八题系列，可谓经典中的经典。 言归正传，本题的任务是，请你计算，具有n个节点的无向连通图有多少种不同的形态。n是一个正整数，1 <= n <= 50,请输出结果。 如： n=3时，输出：4 note：n=3，有如下四种不同的无向连通图 A——-B A——-B A B A——-B . . . . . . . . . . . . C C C C 其中，’.’和’-‘画出的线表示无向图的边，A,B,C表示三个顶点。
示例： 输入： n = 1 输出： 1
分析: 首先要搞清楚,这题必然要用高精度,因为随着n的增长无向连通图的数目的增长将比卡特兰数列更加猛烈.我用的方法是先统计出总共能组成多少无向图,再减去其中不联通的个数.设i个点能组成的无向连通图个数为a[i].n个点之间共有C(n,2)条边可连,总图个数为2^C(n,2).假设图不连通,那么节点1必定在某个连通分量中,由于图不连通,所以节点1所在连通分量节点个数可能为i=1~n-1,则剩下的k=n-i个点可以任意连接,所以a[n]=Σ(i=1->n-1){a[i]*2^C(k,2)}.想清楚之后关键问题就在于高精度。但是在python里面对高精度封装的很好，所以这个题对于Python程序员来说，在语法上面不存在什么难题。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = [1 for _ in range(51)]
a[3] = 4
def pai(n, m):
ta = 1
for i in range(1, m+1):
ta *= (n-i+1)
ta /= i
return int(ta)
for i in range(4, n+1):
temp = 2 ** (i*(i-1) // 2)
for j in range(1, i):
temp -= (a[j] * 2**((i-j) * (i-j-1) // 2)) * pai(i-1, j-1)
a[i] = temp
print(a[n])