【ARC110F】Esoswap 题解

AtC 传送门：ARC110F

对于这类题目，看到之后就应该乱搞。

提供些各种各样的解法：

• 解法一：i 从 0 到 n-1，对于每一个 i 都疯狂对这个位置进行换位操作，直到这个位置上的数是 0 或 i。（目前没有严谨证明。）
• 解法二：每次都在序列中寻找可以一次就交换成功的位置并交换，若交换完之后还没有完成目标，就随机化两个点交换，然后重复刚才的行为。口胡证明如下：
• 解法三：贴一个详细且严谨的讲述。找通解。目标是从小到大顺序排列，但是发现这样不定因素太多了，因为后面在排序的时候会影响到前面已经拍好的序列。所以考虑倒序排列，这样后面排的时候不会影响前面排好的（证明见链接）。倒序排好之后呢？发现一个小性质：1 可以一个一个往后走。所以利用 1 我们就可以巧妙地把倒序排回顺序。