Rotate and Shift

题意

有 $N$ 个位置围成一圈，位置编号为 $0..N-1$ ，初始时第 $i$ 头牛在位置 $i$ 。

给定 $K$ 个活动位置：

text

10 = A_1 < A_2 < ... < A_K < N

每一分钟做两件事：

活动位置上的牛循环移动：A_1 的牛去 A_2，A_2 的牛去 A_3，最后 A_K 的牛去 A_1。
所有活动位置整体加 1，超过 N-1 后回到 0。

求 $T$ 分钟后的牛的顺序。

思路

先看一个小数据逐分钟模拟：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:40
 * update_at: 2026-07-11 16:41
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, k;
int T;
int active_pos[MAXN];
int order_arr[MAXN];
int tmp_value[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> T;
    for (int i = 1; i <= k; i++) {
        cin >> active_pos[i];
    }
    for (int i = 0; i < n; i++) {
        order_arr[i] = i;
    }

    // 小数据暴力：逐分钟模拟活动位置轮转，然后活动位置整体右移。
    for (int t = 1; t <= T; t++) {
        for (int i = 1; i <= k; i++) {
            tmp_value[i] = order_arr[active_pos[i]];
        }

        for (int i = 1; i <= k; i++) {
            int from = i - 1;
            if (from == 0) from = k;
            order_arr[active_pos[i]] = tmp_value[from];
        }

        for (int i = 1; i <= k; i++) {
            active_pos[i]++;
            if (active_pos[i] == n) active_pos[i] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << order_arr[i];
    }
    cout << '\n';

    return 0;
}

暴力每分钟先复制活动位置上的牛，再按循环关系放回去，最后把所有活动位置加一。这个做法复杂度是 $O(KT)$ ，而 $T$ 可能达到 $10^9$ 。

关键变化是：与其让活动位置每分钟右移，不如换一个视角。

如果我们把所有牛的位置每分钟都向左移动一格，同时让活动位置保持不动，那么牛和活动位置之间的相对关系与原过程相同。

在这个“固定活动点”的视角下，活动位置把圆分成若干段：

text

1[A_i, A_{i+1})

其中令 $A_{K+1}=N$ 。

每一段内部的牛会每分钟循环左移一格。也就是说，对于初始在这段内的牛 j：

text

1
2offset = j - A_i
new_offset = offset - T  (mod 段长)

这得到的是固定活动点视角下的位置。

最后还要把视角切回原来的坐标系。原过程中活动位置每分钟右移，所以最后整体再加回 T：

text

1final_pos = (A_i + new_offset + T) mod N

于是可以直接把牛 j 放到 final_pos，每头牛只处理一次。

样例中 N=5, A=[0,2,3], T=4：

段	初始牛	段长	固定视角左移 $4$ 次后	加回 $T$ 后
`[0,2)`	`0,1`	2	`0,1`	位置 `4,0`
`[2,3)`	`2`	1	`2`	位置 `1`
`[3,5)`	`3,4`	2	`3,4`	位置 `2,3`

所以最终顺序是：

text

11 2 3 4 0

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:40
 * update_at: 2026-07-11 16:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, k;
long long T;
int active_pos[MAXN];
int ans[MAXN];

long long mod_positive(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> T;
    for (int i = 1; i <= k; i++) {
        cin >> active_pos[i];
    }
    active_pos[k + 1] = n;

    for (int i = 1; i <= k; i++) {
        int left = active_pos[i];
        int right = active_pos[i + 1];
        int len = right - left;

        for (int cow = left; cow < right; cow++) {
            int offset = cow - left;

            // 固定活动点视角下，区间内部每分钟向左循环移动一次。
            long long new_offset = mod_positive((long long)offset - T, len);
            int final_pos = (int)((left + new_offset + T) % n);
            ans[final_pos] = cow;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

复杂度

每头牛只被处理一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是换参考系：让活动点不动，牛整体反方向移动。

这样原来的动态活动位置变成了固定分段内的循环位移，最后再整体加回 $T$ 即可。

目录

题意

思路

代码

复杂度

总结