[题解] [P4233] 射命丸文的笔记

对于所有 $1\le i\le n$ 求出 $i$ 个点的有哈密顿回路的竞赛图的哈密顿回路数量的期望。

$1\le n\le 100000$

题目链接

---

思路

（这篇题解主要就是补一下大多数题解不屑于提到的证明）

首先 $n$ 个点所有图的哈密顿回路总数可求，就是 $(n-1)!\cdot2^{\binom n2-n}$。因为哈密顿回路一共有 $(n-1)!$ 种，然后定下一个哈密顿回路其它的边随便定向即可。

我们考虑求有哈密顿回路的图的数量。首先有个定理：
$$
\text{竞赛图有哈密顿回路}\iff\text{竞赛图强联通}
$$
充分性显然，考虑证必要性。我们考虑归纳，删掉 $n$ 号点后剩下的点会形成一些极大的强联通块，并且有唯一的拓扑序，假设按这个序排出来是 $S_1,S_2,\cdots,S_k$，且 $S_i$ 的每个点都向 $S_{i+1}$ 的每个点有连边。

首先考虑 $k>1$ 的情况，那么由于整个图强联通，所以 $n$ 号点必然向 $S_1$ 中至少连了一条边，$S_k$ 中至少向 $n$ 连了一条边，又由于对于所有 $S_i$ 我们已经归纳证明了它有一条哈密顿回路，那么我们可以构造出 $n\rightarrow S_1\rightarrow S_2\rightarrow\cdots\rightarrow S_k\rightarrow n$ 的一条哈密顿回路。

然后是 $k=1$ 的情况。我们考虑到由于至少有一条 $S_1\rightarrow n$ 的边和一条 $n\rightarrow S_1$ 的边，那么设 $S_1$ 的哈密顿回路序列 $a_i$（循环），那么必定有一个 $i$ 使得存在 $a_i\rightarrow n$ 且存在 $a_{i+1}\leftarrow n$，那么这样子我们就可以构造出一条哈密顿回路。

证明完毕。现在我们就是要求 $n$ 个点的强联通竞赛图数量。我们考虑计算非强联通竞赛图的数量，发现一个非强联通竞赛图是唯一地由一个 极大的 强联通竞赛图和其它点任意连边构成的。写出来是：
$$
f_i=2^{\binom i2}-\sum_{j=0}^{i-1} \binom ij f_j\cdot 2^{\binom{i-j}2}
$$
然后拆一下再移项：
$$
\sum_{j=0}^i\frac{f_j}{j!}2^{\binom {i-j}2}=2^{\binom i2}
$$
然后设 $f_i$ 的 EGF $F(x)$，$G(x)=\sum_{i=0}^\infty 2^{\binom i2}x^i$，那么我们有（注意常数项）：

$$ \begin{aligned} F(x)\cdot G(x)+1&=G(x)\\ F(x)&=\frac{G(x)-1}{G(x)} \end{aligned} $$

然后多项式求逆就做完了。注意 $n$ 比较小要特判。

代码

mivik.h

代码