P4778 Counting swaps

· · 题解

对每个 i 向 p_i 连边，表示初始在位置 i 上的数想到位置 p_i 上去。这样得到若干个环。明显环间交换不优，所以我们只需考虑一个环的最优交换次数，然后用组合数给所有环的操作序列分配标号。对于一个环，考虑对于它表示的序列交换两个数后，环会分裂成两个小环。因此可以得出大小为 n 的环的最优交换次数 f_n 的递推式（当两点距离为 \frac{n}{2} 时选法是 \frac{n}{2}，其它都是 n。用 \binom{n-2}{i-1} 分配两个环的操作的标号）

f_1=1,f_n=\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n-2}{i-1}f_if_{n-i}(2i==n?\frac{n}{2}:n)

（这个递推式对结论的证明没有用处）

这个式子可以分治 FFT 求、也可以牛顿迭代，但这并不是重点，重点是大多数题解提出但没有证明的结论 f_n=n^{n-2}（这就是有标号无根树个数！）。为此我咨询了大佬 \text{S}\color{red}\text{aInT7}，得到了基于构造双射法的组合意义证明：

每次操作 p_x,p_y 时，在一个图 G 中加一条边 (x,y)，由上面的讨论知道这是一棵树。一个尝试是将每种操作与它对应的树建立双射，但这显然是错的，因为很容易举出例子发现相同的操作集合但不同的操作顺序得到了相同的树。但是我们注意到确定一棵树以及确定了 n-1 条边的删除顺序后（这样的组合对象有 n^{n-2}(n-1)! 种），我们可以倒序操作，倒着 swap，那么每次就是对于两个环在环间交换元素，容易发现这会使两个环合成一个大环，因此存在一个唯一的环使得这个操作是合法的。因此，我们对于每个环的所有合法操作，将其与边有顺序的有标号无根树建立了双射。而显然对于每个环合法操作都是相同的，所以对于单个环合法操作个数为 \frac{n^{n-2}(n-1)!}{(n-1)!}=n^{n-2}。

另外顺便提一下，这题的复杂度它应该是 O(n) 的。只需不提前预处理 f_n，而是在每次用到的时候算。