AT_arc110_f 题解

xuchuhan · 2025-11-20 17:29:59 · 题解

好玩的诈骗题。

模拟赛时给了一个启发性的 Subtask 即 p_0=n-1,p_i=i-1(i\neq 0)。一种做法是对于位置 0 反复操作 n-1 次即可构造。

发现这个题的构造方式很开放，所以需要找到一个固定的操作（组）策略。上述做法启发我们对着一个位置反复操作。

结论：一个位置 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\sim 0 操作 n 次变为 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。

所以最后输出 n 个 n-1\sim 0 即可。

#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;
}