ABC 436 总结

来源：ABC 436 E

题目复述：

给定长度为 $n$ 的排列 $a$，每次可以交换任意两个位置 $i, j$ 上的数。
目标是让所有 $a_i = i$。

设最少操作次数为 $k$。
问有多少种不同的第一次交换 $(i,\ j)$（$i < j$），
使得存在后续操作，能在正好 $k$ 步内完成排序。

赛时思路：

感觉像之前见过的一道题，想了想好像是浙大的一道题目，和这题差不多，那题是找出置换环的数量，回到这题。然后当时想偏了，导致找到正解的时候只有 $20s$ 了，就没写出来。

正解：

现在正解还没出来，我就先按照我的已 A 思路来写：

最少操作次数 $K = n - C$，
其中 $C$ 是排列分解出的置换环数量。

要让总操作次数保持最少，每次交换必须在同一个环内进行，这样环数 $+1$，最终每个环长度为 1 就排好序了。

所以第一步也必须是同一环内交换，否则环数 $-1$，总步数至少 $n - (C-1) = K+1$ 步。

答案就是所有环内无序对的总和：

$$
\sum_{环} \frac{l(l-1)}{2}
$$

其中 $l$ 是环的长度，复杂度 $O(n)$。