自动搬运

查看原文

来自洛谷，原作者为

	lrqlrq250 AFOed, さよなら

搬运于2025-08-24 21:15:09，当前版本为作者最后更新于2023-06-21 19:31:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意转述

给定一个长度为 $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;
}