[NC记录]ARC110F Esoswap
command_block
2021-10-27 08:07:32
**题意** ： 给出一个 $0\sim n-1$ 的排列 $P_{0\sim n-1}$。
可以使用下列操作至多 $2\times 10^5$ 次：
- 选定 $0\leq i<n$ ，交换 $P_i,P_{(i+P_i)\bmod n}$ 。
目标是将 $P$ 排序，构造一种方案或指出无解。
$n\leq 100$ ，时限$\texttt{2s}$。
------------
构造题，先尝试观察一些特化方案。
若不断操作 $i$ ，记初始时 $P_i=a$ ，可以发现，若要把 $a$ 拿回来除非 $P_i$ 再次为 $a$ ，可 $a$ 已经走了。
所以，重复执行操作必然会得到不同的数，直到得到 $0$ 为止。
首先不断执行 $n-1$ ，将 $0$ 移到 $n-1$。
然后依次不断执行 $n-2$ ，拿到 $1$ 为止；执行 $n-3$ ，拿到 $2$ 为止……
可以发现，在拿 $i$ 时，$0\sim i-1$ 都已经被固定，可能跳过的只有 $i+1\sim n$ ，而这些数不会影响到后面的 $0\sim i-1$ 。
于是我们用 $O(n^2)$ 次操作使得序列降序。
考虑逐渐对后缀排序，假设 $0\sim i-1$ 已经排好序，接下来要 插入 $i$。
此时对 $i$ 操作，恰可以将 $i$ 与 $P_n$ 交换。
注意到 $1$ 可以任意移动，我们将 $1$ 移到 $n$ ，然后操作 $i$ ，然后将 $1$ 移回去即可。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 105
#define MaxS 200500
using namespace std;
int n,tn,p[MaxN],ans[MaxS];
void mdf(int i){
ans[++tn]=i;
swap(p[i],p[(i+p[i])%n]);
}
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)scanf("%d",&p[i]);
for (int i=n-1;i;i--)while(p[i]!=n-i-1)mdf(i);
mdf(n-2);
for (int i=n-3;i>=0;i--){
for (int j=i+2;j<n-1;j++)mdf(j);
mdf(i);mdf(i);
}
printf("%d\n",tn);
for (int i=1;i<=tn;i++)printf("%d\n",ans[i]);
return 0;
}
```