B3802 [NICA #1] 交换 题解

· · 题解

题意转述

给定一个长度为 n 的排列 a，执行 m 次操作，其中的第 i 次操作内容为交换 n - ((i - 1) \bmod (n - 1)) 和 n - ((i - 1) \bmod (n - 1)) - 1，问 m 次操作后该排列变成了什么样子。

解题思路

首先，我们发现 m 的取值范围太大了。

由于我们不可能手动模拟这么大的数，因此这暗示我们这种操作会有周期。

结论：在每执行 n \times (n - 1) 次操作后，排列会变回原样。

比较朴素地证明一下：考虑 n - 1 次操作（不妨认为这是一轮），操作一轮后的数组会有什么变化？

考虑涉及交换 n 的操作只有“和 n - 1 交换”这一个，因此一轮后 n 会在 n - 1 的原位上。同样的，涉及 n - 1 的操作是“先和 n 交换，再和 n - 2 交换”，由于只有最后一次关于它的交换决定其最终位置，可得 n - 1 最终会在 n - 2 的原位上。以此类推，最后 1 被换到 n 的原位上。

因此每进行“一轮”操作，相当于每个数都错位 1 次，而错位 n 次后就会回到原序列的状态，因此循环节长度为 n \times (n - 1)。

如果上面部分没有太看明白，可以自己手敲一个暴力模拟的程序体验一下。

至此，我们一边输入一边取模，就可以剔除所有冗余的循环节，控制 m 最终小于 n \times (n - 1)。

但是 n \leq 10^5，即此时 m \leq 10^{10} 左右，依然无法支持我们模拟。

于是我们回到上面“错位”的性质。从数的角度上讲，“错位”指的是一个数 k 来到了 k - 1 的位置上。而从位置的角度上将，“错位”指的是这个位置上的数加一（超过 n 则变回 1），这两种表述是等价的，但我们发现后者显然比前者好维护，因为前者依然是交换，但后者只是每个位置增加一个特定的值，再取模。不难发现增加的值为 \lfloor \frac{m}{n-1} \rfloor。

至此，我们就可以 O(n) 统计出所有“错位”的操作对序列造成的影响了。剩下的不够造成一次“错位”的操作继续手动模拟即可。

时间复杂度 O(n + \log_{10} m)，可以通过本题。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long n, m;
int a[N], pos[N];

inline long long readm(){
    int f = 1;
    long long x = 0;
    char c = getchar();
    while (!isdigit(c)){f = c == '-' ? -1 : 1; c = getchar();}
    while (isdigit(c)){x = ((x << 1) + (x << 3) + (c ^ 48)) % (n * (n - 1)); c = getchar();}//一边读入一边取模
    return f * x;
}

int main(){
    scanf("%d", &n);
    m = readm();
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    int t = m / (n - 1), left = m % (n - 1);
    if (t){
        for (int i=1; i<=n; i++){
            a[i] = (a[i] + t) % n ? (a[i] + t) % n : n;
        }//统计错位造成的影响
    }
    for (int i=1; i<=n; i++) pos[a[i]] = i; 
    for (int i=1; i<=left; i++){
        int p1 = n - (i - 1) % (n - 1), p2 = n - (i - 1) % (n - 1) - 1;
        swap(a[pos[p1]], a[pos[p2]]);
        swap(pos[p1], pos[p2]);
    }//手动模拟
    for (int i=1; i<=n; i++) printf("%d ", a[i]);
    return 0;
}