本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-01 22:10:30

前言：

主要是记录一下 $\text{\color{black}{皎}\color{red}{月半洒花}}$ 大佬的讲题思路

题目翻译：

给定一个 $n$，求由 $n$ 个点组成的无向连通图个数。
多测

正文：

用 $h_n$ 代表 $n$ 个点组成的无向图个数，$f_n$ 代表 $n$ 个点组成的无向连通图个数，$g_n$ 代表 $n$ 个点组成的无向不连通图个数。
来想一下每一项的计算方式：

• $h_n$
  $n$ 个点两两之间互相连边，一共有 $C_n^2$ 条。而每一条边可以存在也可以不存在，所以一共有 $2^{C_n^2}$ 种情况。
• $g_n$
  显然，$g_n = h_n - f_n$
• $f_n$
  可以将图分割成，「包含 $1$ 的连通块」和「其他点」两个集合。然后枚举 「包含 $1$ 的连通块」 集合的大小从 $1 \rightarrow n-1$。集合大小为 $i$ ，可以看作在 $n-1$ 个点中挑选 $i-1$ 个非 $1$ 的点，也就是 $C_{n-1}^{i-1}$。同时这 $i$ 个点还会以 $f_i$ 种形态组成连通图。另外 $n-i$ 个没有选上的点将以 $h_{n-i}$ 种形态组成图。最后答案就是 $\sum_1^{n-1} C_{n-1}^{i-1} \cdot f_i \cdot h_{n-i}$

现在知道了转移方法，就可以做了。