Rotate and Shift

题目描述

注意：本题时间限制为 4s，是默认的 2 倍。 为了庆祝春天的到来，农夫约翰的 $N$ 头奶牛（$1 \leq N \leq 2 \cdot 10^5$）发明了一种有趣的新舞蹈：它们站成一个圆圈，并以一种可预测的方式重新排列。

具体来说，圆圈上有 $N$ 个位置，按顺序编号为 $0$ 到 $N-1$，其中位置 $0$ 紧跟在位置 $N-1$ 之后。每个位置上都有一头奶牛。奶牛也按顺序编号为 $0$ 到 $N-1$。初始时，奶牛 $i$ 位于位置 $i$。

给定一组“活跃”的位置 $0=A_1<A_2< \ldots< A_K<N$，表示这些位置上的奶牛将是下一次要移动的奶牛（$1 \leq K \leq N$）。

在舞蹈的每一分钟内，会发生两件事。首先，活跃位置上的奶牛进行旋转：位置 $A_1$ 的奶牛移动到位置 $A_2$，位置 $A_2$ 的奶牛移动到位置 $A_3$，依此类推，位置 $A_K$ 的奶牛移动到位置 $A_1$。这 $K$ 次移动同时发生，因此旋转结束后，所有活跃位置仍然恰好各有一头奶牛。

接着，活跃位置本身整体平移： $A_1$ 变为 $A_1+1$，$A_2$ 变为 $A_2+1$，依此类推（如果某个活跃位置满足 $A_i = N-1$，则该 $A_i$ 会绕回到 $0$）。

请计算舞蹈进行 $T$ 分钟后奶牛的排列顺序（$1\le T\le 10^9$）。

输入格式

第一行包含三个整数 $N$、$K$ 和 $T$。 第二行包含 $K$ 个整数，表示初始的活跃位置集合 $A_1,A_2, \ldots A_K$。注意 $A_1 = 0$，并且这些数按递增顺序给出。

输出格式

输出进行 $T$ 分钟后的奶牛顺序，从位置 $0$ 上的奶牛开始输出，用空格分隔。

5 3 4
0 2 3

1 2 3 4 0

提示

对于上面的例子，前四个时间步的奶牛顺序和 $A$ 如下： Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3] T = 1: order = [3 1 0 2 4] T = 1: A = [1 3 4] T = 2: order = [3 4 0 1 2] T = 2: A = [2 4 0] T = 3: order = [2 4 3 1 0] T = 3: A = [3 0 1] T = 4: order = [1 2 3 4 0] SCORING: Inputs 2-7: $N \leq 1000, T \leq 10000$ Inputs 8-13: No additional constraints. Problem credits: Claire Zhang

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze