CF2140A Shift Sort 题解

本文用 表示轮换位置 的元素（即，），用 表示交换位置在 的元素。

假如我们要进行的轮换是 。由鸽巢原理可知， 三个数中必有两个数是相同的元素。假如 ，我们可以将这个轮换写成 的形式。注意这个轮换和原来的轮换实际上是一个，相同的位置最终到的位置是不变的（可以代入试一下）， 的情况类似。因此任意轮换都可以写成 满足 的形式。

轮换有一个性质，，证明方法就是每个元素都代进去试一下。由于 ，因此实际上我们要进行的轮换就是 。因此每个轮换操作都等价于一次交换操作。

那么使用交换操作将这个序列排序是简单的。只需要统计一下 的个数 ，统计后 位中不是 的位置个数就是答案了。