[集训队作业2013] 城市规划
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过，阿狸的国家有 \(n\) 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出 \(n\) 个点的简单 (无重边无自环) 有标号无向连通图数目。
由于这个数字可能非常大, 你只需要输出方案数对 \(1004535809\) ( \(479 \times 2 ^{21} + 1\) ) 取模即可。
连通这个条件很不好求，考虑转化一下。
考虑一个普通图，不要求连通，那么这张图一定是由若干张连通图组成的。
那么把连通图看作一个元素的话，其生成集合即为任意普通图。
我们知道对 EGF \(\exp\) 一下是原组合对象的生成集合的 EGF。
设连通图的 EGF 为 \(A\)，普通图的 EGF 为 \(B\)，那么有
\[\exp A = B \]从而有
\[A = \ln B \]而以普通图作为组合对象处理简单很多了。
一张 \(n\) 个点的完全图有 \(\frac {n(n + 1)}{2}\) 条边，而每条边都可连可不连，因此方案数是 \(2 ^ {\frac {n(n + 1)}{2}}\)。所以：
\[B = \sum_n 2 ^ {\frac {n(n + 1)}{2}} \frac {x^n}{x!} \]取个 \(\ln\) 即可。
标签：方案,城市规划,frac,阿狸,连通,EGF From： https://www.cnblogs.com/AzusidNya/p/18248555