AT_arc110_f 题解

结论：一个位置 $i$ 反复操作 $n-1$ 次后必然有 $p_i=0$。

证明：显然当交换到 $0$ 后就一直是 $0$ 不会动了，那么只需要证明一个位置反复操作不超过 $n-1$ 次可以交换到 $0$。设初始 $p_i=v(v\neq 0)$，那么 $v$ 会被换到 $p_{i+v}$ 上去。此后 $p_i$ 想要再次换回 $v$ 就必须有 $p_i=v$，与 $p_{i+v}=v$ 矛盾。也就是说，$p_i$ 每次都会换到一个新的数，那么至多 $n-1$ 次可以换到 $0$。

• 最开始是 ? ? ? ... ?。
• 连续操作 $n-1$ 后变为 ? ? ? ... 0。
• 连续操作 $n-2$ 后变为 ? ? ? ... 0 1。原因是如果 $p_{n-2}$ 想要为 $0$ 需要从 $p_{n-1}$ 换。那么需要用 $p_{n-2}=1$ 去换，交换后就有 $p_{n-2}=0,p_{n-1}=1$。
• 连续操作 $n-3$ 后变为 ? ? ? ... 0 1 2。同理，$p_{n-3}$ 需要得到 $1$ 才能去换 $p_{n-2}=0$，那么 $p_{n-3}$ 需要得到 $2$ 才能去换 $p_{n-1}=1$。那么最后 $2$ 被换到了 $p_{n-1}$，$1$ 被换到了 $p_{n-2}$，$0$ 被换到了 $p_{n-3}$。
• 同理一路换下去。最后是 0 1 2 ... n。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n,cout<<n*n<<"\n";
	for(int i=n-1;i>=0;i--)for(int j=1;j<=n;j++)cout<<i<<"\n";
	return 0;
}