题解：P14720 [RMI 2025] 鼠皇 / King of rats

· · 题解

根据平面图的欧拉公式（显然其在期望意义下同样成立），对于一个连通块来说，有：E(V)-E(E)+E(F)=2

由于欧拉公式中的 F 是包括最外层的大平面的，为了简化计算，我们假设 F 不包括最外层的大平面。

于是就有：

\text{对于单个连通块：} E(V)-E(E)+E(F) &= 1\\ \text{对于整个图：} E(V)-E(E)+E(F) &= E(S) \end{aligned}

其中 S 代表连通块个数。

上面的公式中 E(V) 就是 k，只需考虑如何计算 E(E) 和 E(F)，即相邻的都是 1 的点对的期望，以及全 1 的 2\times 2 矩阵的数量的期望。

对于 E(E) 显然选择 k 个点涂黑，使得钦定的一对相邻点被涂黑的方案数是 \binom{2n-2}{k-2}，于是对于每一对点，都被涂黑的概率就是 \frac{\binom{2n-2}{k-2}}{\binom{2n}{k}}，乘上总对数 3n-2，再化简，得到 E(E) 就是 \frac{k(k-1)(3n-2)}{2n(2n-1)} 。

使用同样的套路推到，就能得到 E(F)，这一部分留给读者自己推导，这里只给出结果： E(F)=\frac{k^{\underline{4}}(n-1)}{2n^{\underline{4}}}。

代码很简单，照着上面的公式计算就行，核心代码 20 行以内。