带标号的连通图计数 bzoj3456 城市规划
这是一个非常经典的问题。我们考虑容斥，那么就是图的数量减去不连通图的数量。计算不连通图的数量时，我们考虑枚举$1$号点所在的连通块大小（这样一定不重不漏），那么得到：
拆组合数：
这是一个卷积的形式，可以分治FFT解决。
带标号的强连通竞赛图计数 luogu4233 射命丸文的笔记
问题：求随机拿出一个有哈密顿回路的竞赛图，图中哈密顿回路数量的期望值。
Sol：问题可以转换成“所有竞赛图中的哈密顿回路的数量的和”除以“包含哈密顿回路的图的数量”。前者非常好算：$(n-1)!2^{C_n^2 - n}$，即枚举每一个哈密顿回路（数量等于圆排列的数量），然后计算它被多少竞赛图包含。有$n$条边已经确定，剩下的$C_n^2 - n$条边，每条边都有两个方向可以选择，所以是$2^{C_n^2 -n}$。
现在的问题是：求包含$n$个点的，存在哈密顿回路的竞赛图的数量。等价于求包含$n$个点的强连通的竞赛图的数量。
那么设$f(n)$表示包含$n$个点的强连通的竞赛图的数量，设$g(n)$表示包含$n$个点的竞赛图的数量。则$g(n) = 2^{C_n^2}$。仍然考虑与前一题类似的容斥。但是，如果我们枚举$1$号点所在的强连通分量的大小，其他的强连通分量可能有边连向这个强连通分量，这个强连通分量也可能有边连出去，可能会导致我们枚举的这个“强连通分量”是图中一个强连通分量的子图，非常麻烦。那么我们可以考虑枚举拓扑序最靠后的那一个强连通分量，即没有出边的那一个。由于这是竞赛图，这样的强连通分量在一个确定的图中一定是唯一的（可以这样想：如果有两个这样的强连通分量，那么它们之间一定有一条边，那么它们中的一个就一定有出度，矛盾）。于是得到：
这又是一个卷积了。分治FFT解决。
带标号的无根树的计数：prufer序列
求一棵树的prufer序列
每一次选择编号最小的叶子，将这个叶子从图中删除，并且将与它相邻的点的编号加入序列。直到图中只剩下两个点为止。
由prufer序列还原一棵树
找出未在序列中出现的并且未被标记的编号最小的点（树上编号最小的叶子），让它和序列开头的点连边，标记它，然后删掉序列开头的元素。当只剩下两个点未被标记的时候就停止，在它们之间连边，就完成了。
可以看出，prufer序列一定是一个长度为$n-2$的，所有点都在$[1,n]$的序列；一个点在prufer序列中出现的次数等于它在树上的度数。
从上面的过程可以看出：带标号的无根树和prufer序列是一一对应的关系。因此，我们可以推出：包含$n$个点的带标号的无根树的数量，等于长度为$n-2$，所有数都在$[1,n]$的序列的数量，等于$n^{n-2}$。
而如果题目给定了每个点的度数，那就等于给定了每个点在prufer序列中出现的次数，那么就是可重排列数。（bzoj 1211 1005）