好题小记

CF838D Airplane Arrangements

题目传送门

很高妙的题。

直接计算不太好做，考虑把链首尾接起来拼成环，但注意到直接拼就无法判不合法，所以在 $1$ 和 $n$ 中间插入一个 $n+1$ 号点，若 $n+1$ 号点被覆盖则不合法。

考虑对于所有方案计算 $n+1$ 号点被覆盖的概率，注意到任意一种覆盖情况都可以通过同一个置换达到 $n+1$ 种情况，则可称其为一个等价类，而等价类集合包含所有元素且不交，所以一个点被覆盖的概率等于在一个等价类中被覆盖的概率，即 $\frac{m}{n+1}$，所以合法概率即 $n+1$ 号点不被覆盖的概率，即 $\frac{n+1-m}{n+1}$，而总方案数为 $(2 \times (n+1))^m$，所以答案为 $(2 \times (n+1))^m \times \frac{n+1-m}{n+1}$。