Rotate and Shift (USACO Bronze 2023 US Open)

此题看似很复杂，牛跳来跳去，还有会移动的“活跃位置”。所以我们一步步来找规律。

首先，所题目所述，每过一分钟，所有的活跃位置 $A_j$ 延圆圈转动一格。这时，如果我们集中注意力关注一头固定的牛，我们可以看到它永远是被同一个“活跃位置”覆盖的：

假设一头牛开始的位置是 $i$ ，如果它“对应”的活跃位置是 $A_j$ ，“对应”的意思是或者一开始 $A_j=i$ ，或者经过若干次转动之后 $A_j$ 是第一个指向 $i$ 的活跃位置。当 $i$ 被 $A_j$ 覆盖的时候， $i$ 就会被转移到 $A_{j+1\mod K}$ 的位置。然后再次经过 $A_{j+1 \mod K}-A_j$ 分钟后， $i$ 又会被 $A_j$ 再次覆盖，重复这个过程。

所以 $i$ 的移动规律就是，从第一次被 $A_j$ 覆盖开始，每次发生覆盖时向前移动 $A_{j+1 \mod K}-A_j$ 步，而因为所有 $A$ 在圆圈上同步移动，这个步长是一个固定位。

通过这个规律，我们就可以对这头牛 $\mathcal{O}(1)$ 计算最终位置了，所以整体算法是 $\mathcal{O}(N)$ 的。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, k, t;
int A[200005];
int ans[200005];
 
int main() {
    scanf("%d%d%d", &n, &k, &t);
    for (int i = 0; i < k; i++)
        scanf("%d", &A[i]);
 
    int j = 0;      // A1 == 0
    for (int i = 0; i < n; i++) {
        if (j < k-1 && i == A[j+1])
            j++;
        int t0 = i - A[j];
        int step = j == k-1 ? n-A[j] : A[j+1]-A[j];
        int times = 0;
        if (t >= t0)
            times = (t-t0 + step-1) / step;
        ans[(i + (ll)step * times) % n] = i;
    }
    for (int i = 0; i < n; i++)
        printf("%d ", ans[i]);
 
    return 0;
}