【2022 NOIP 模拟赛 25】取啊 做题记录

小可可又在造数据，只不过这次是一个联通图。

小可可要造一个 $n$ 个点的联通图，由于她非常懒，于是决定每次在 $[1, n]$ 中独立地等概率随机两个点 $u, v$（可以相同），然后将 $u, v$ 之间连一条边。

小可可发现要等到整张图联通需要不少时间，于是问你期望连多少次边后整张图联通，答案对一个质数 $p$ 取模。

$1\le n\le 100$。

设 $dp_{n, k}$ 表示 $n$ 个点的图，经过 $k$ 次之后仍然不联通的概率。

枚举与 $1$ 联通的点个数，有：

$\begin{aligned} dp_{n, k} =&\sum\limits_{i = 1}^{n - 1} \sum\limits_{j = 0}^k \binom{n - 1}{i - 1} \binom{k}{j} (1 - dp_{i, j}) \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j}\\ &= \sum\limits_{i = 1}^{n - 1} \sum\limits_{j = 0}^k \binom{n - 1}{i - 1} \binom{k}{j} \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j} - \binom{n - 1}{i - 1} \binom{k}{j} dp_{i, j} \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j}\\ &= \sum\limits_{i = 1}^{n - 1} \binom{n - 1}{i - 1} \left( \frac{i^2 + (n - i)^2}{n^2} \right) ^k - \sum\limits_{i = 1}^{n - 1} \sum\limits_{j = 0}^k \binom{n - 1}{i - 1} \binom{k}{j} dp_{i, j} \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j} \end{aligned}$

归纳证明 $dp_{n, k} = \sum\limits_{l = 0}^{n^2 - 1} f_{n, l} \left( \frac{l}{n^2} \right) ^k$，其中 $f_{n, l}$ 是递推得出的系数。

等式前面一部分形式已经符合此形式，考虑后面一部分：

$\begin{aligned} &= \sum\limits_{i = 1}^{n - 1} \sum\limits_{j = 0}^k \binom{n - 1}{i - 1} \binom{k}{j} dp_{i, j} \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j}\\ &= \sum\limits_{i = 1}^{n - 1} \binom{n - 1}{i - 1} \sum\limits_{l = 0}^{i^2 - 1} f_{i, l} \sum\limits_{j = 0}^k \binom{k}{j} \left( \frac{l}{i^2} \right) ^j \left( \frac{i^2}{n^2} \right) ^j \left( \frac{(n - i)^2}{n^2} \right) ^{k - j}\\ &= \sum\limits_{i = 1}^{n - 1} \binom{n - 1}{i - 1} \sum\limits_{l = 0}^{i^2 - 1} f_{i, l} \left( \frac{l + (n - i)^2}{n^2} \right) ^k \end{aligned}$

于是

$\sum\limits_{l = 0}^{n^2 - 1} f_{n, l} \left( \frac{l}{n^2} \right) ^k=\sum\limits_{i = 1}^{n - 1} \binom{n - 1}{i - 1} \left( \frac{i^2 + (n - i)^2}{n^2} \right) ^k-\sum\limits_{i = 1}^{n - 1} \sum\limits_{l = 0}^{i^2 - 1} f_{i, l} \binom{n - 1}{i - 1}\left( \frac{l + (n - i)^2}{n^2} \right) ^k$

那么可以 $O(n^4)$ 求出 $f(n,l)$。

答案即为 $\sum\limits_{i = 0}^{n^2 - 1} \sum\limits_{k = 0}^{+\infty} f_{n, i} \left( \frac{i}{n^2} \right) ^k = \sum\limits_{i = 0}^{n^2 - 1} f_{n, i} \frac{n^2}{n^2 - i}$。