【POJ 1737】Connected Graph

题目传送门:http://poj.org/problem?id=1737
中文题面:《算法竞赛·入门经典·训练指南》P112

想一想,貌似直接容斥之类的都上不了
于是就不会做了 QAQ
mvr5zj9l7yp

设f(n)为连通图个数,g(n)为不联通的个数,h(n)为总方案数
首先h(n)可以直接算:\(h(n) = {2^{\frac{{n(n – 1)}}{{\rm{2}}}}}\)
又f(n)+g(n)=h(n),所以我们只需要求解g(n)即可

考虑1所在的联通块,假设有i个点,则这部分的方案数就是f(i)
又考虑剩余点对于答案的贡献,因为不一定联通,所以为h(n-i)
所以\(g(n) = \sum\limits_{i = 1}^{n – 1} {f(i) \cdot h(n – i)} \)
于是f(n)用h(n)-g(n)就可以辣!

因为原题要上高精度
所以代码什么的还是算了吧?
_(:з」∠)_