P7474 「C.E.L.U-02」学术精神
原题
题目挺好的，数据范围诈骗挺烂的
首先第一问没什么好说的，连边成功的概率为\(\frac{n-1}{n}\)，因此连边成功的期望次数为\(\frac{n}{n-1}\)
又因为要连\(n\)次边，因此边期望个数为\(\frac{n^2}{n-1}\)
主要是第二问，这里我先说我自己想出来的做法
方法1：
首先我们发现选点的顺序是无所谓的，证明显然
我们先考虑如果按照编号顺序操作，操作过程中的联通块是长什么样的
容易发现联通块分成以下几种：
-
联通块大小为\(1\)，即在操作过程中还未被考虑到
-
联通块中有为被考虑到的点，此时这个联通块是一棵树
-
联通块中没有被考虑到的点，此时这个联通块是一个基环树
我们发现对于\(1\)和\(2\)种情况，我们可以让别的联通块和这些联通块合并；但对于第\(3\)种情况是不可能由其内部的点向外合并，只可能是别的\(1,2\)种联通块来合并第\(3\)种。因此我们对于\(1,2\)种联通块称为“活联通块”，第\(3\)种联通块称为“死联通块”；类似的，称已经向外连边的点为“死点”，没有向外连边的点为“活点”
我们容易发现在操作结束后，所有联通块肯定都是死联通块，否则肯定存在没连边的点
于是我们想到一个比较好的\(dp\)顺序：按照联通块\(dp\)。具体的，如果当前点所在的联通块还是活联通块，那他就会和死点或和活点合并。其中分成以下几种情况：
-
和死点合并，这个死点来源于自身所在的联通块；操作后会使联通块个数+1
-
和死点合并，这个死点来源于不同于自身的死联通块；操作后联通块个数不变
-
和活点合并
对于这三种情况分别\(dp\)处理即可，难点在于考虑联通块个数的贡献是在之前加还是之后加。
最终复杂度\(O(n^2)\)，想过1e4有点困难
方法2：
我们发现对于每一个联通块，里面都是一棵基环树
换言之，联通块的数量 \(=\) 环的数量
因此我们考虑联通时产生环的期望个数
由于知道\(E = \frac{sum}{cnt}\)，因此我们分别计算\(sum\)和\(cnt\)
显然，每个节点有\(n-1\)种选法，因此\(cnt = (n-1)^n\)
然后考虑记录环的总数。我们按照环的大小进行不同考虑，设环大小为\(i \ (2 \leq i \leq n)\)，则对于一个确定的\(i\)，其方案数为\(\binom{n}{i} \times (i-1)! \times (n-1)^{n-i}\)，其中\(\binom{n}{i}\)表示从\(n\)个点中选\(i\)个点作为环上的点，\((i-1)!\)表示这些点的连边方案，\((n-1)^{n-i}\)则表示剩下\(n-i\)个点随便连边的方案
因此\(sum = \sum_{i=2}^{n}{\binom{n}{i} \times (i-1)! \times (n-1)^{n-i}}\)
容易得到最终答案：
最终复杂度\(O(n)\)