首先，我们很容易就能得出一个显而易见的结论：
若令原数组为 \(order\)，\(K\) 个活跃位置分别为 \(A_1,A_2,...,A_K\)，则
\[order_{A_1} \to order_{A_2},order_{A_2} \to order_{A_3},...,order_{A_K} \to order_{A_1} \]的操作就等价于将 \(order\) 数组顺时针旋转 \(x\) 次，即
\[order_1 \to order_2,order_2 \to order_3,...,order_N \to order_1 \]再进行上述操作，最后逆时针旋转 \(x\) 次转回来。
因为顺时针和逆时针的旋转方向是相反的，都旋转 \(x\) 次正好抵消，所以上述结论的正确性也是显然的。
根据上述结论，题目所说的操作流程可以如下：
\[1. \ R \]\[2. \ +1,R,-1 \]\[3. \ +2,R,-2 \]\[\cdot \cdot \cdot \]\[T. \ +(T-1),R,-(T-1) \]（其中 \(R\) 表示将 \(order\) 数组按 \(A\) 数组轮换的操作，\(+x\) 和 \(-x\)表示顺时针 / 逆时针旋转 \(x\) 次 \(order\) 数组的操作，\(x.\) 表示第 \(x\) 分钟进行的操作。）
这个过程中的顺时针和逆时针可以抵消，于是化简后的结果如下：
\[1. \ R,+1 \]\[2. \ R,+1 \]\[3. \ R,+1 \]\[\cdot \cdot \cdot \]\[T. \ R,+1,-T \]这样化简之后，每分钟的操作都变成了 \(R,+1\)，我们称这样的一次操作为 \(S\)。
于是整个题目的操作流程变成了每分钟进行一次 \(S\) 操作，最后逆时针旋转 \(T\) 次即可。
但是每次 \(S\) 操作的时间都是 \(O(N)\) 的，总时间复杂度还是 \(O(TN)\)，和暴力并无区别。
那么如何加快 \(S\) 操作？既然朴素地旋转、轮换是不行的，那么我们就考虑使用倍增加快 \(S\) 操作的速度。
具体而言：
-
建立倍增数组数组 \(jmp\)，其中 \(jmp_{i,j}\) 表示用 \(2^j\) 次 \(S\) 操作能够把 \(i\) 挪到的位置。
-
首先预处理 \(jmp\) 数组，令 \(jmp_{b_i,0}=i\)，并令 \(jmp_{i,j}=jmp_{jmp_{i,j-1},j-1}\)（即从 \(i\) 用 \(2^{j-1}\) 次 \(S\) 操作挪到的位置开始再进行 \(2^{j-1}\) 次 \(S\) 操作。
-
接着枚举 \(2\) 的 \(k\) 次幂，若 \(2^k \le T\) 则进行 \(2^k\) 次 \(S\) 操作。
最后别忘了逆时针再旋转 \(T\) 次就可以了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,t,tt; //tt是t的备份
int jmp[200031][64]; //倍增数组
int sor1[200031],sor2[200031],rot[200031],tmp[200031]; //order 数组，order 数组备份、A 数组、旋转辅助数组
void rotate1(){ //R 操作
memset(tmp,-1,sizeof(tmp));
for(int i=1;i<k;i++) tmp[rot[i]]=sor2[rot[i-1]];
tmp[rot[0]]=sor2[rot[k-1]];
for(int i=0;i<n;i++)
if(tmp[i]+1) sor2[i]=tmp[i];
}
void rotate2(){ //顺时针旋转
memset(tmp,0,sizeof(tmp));
for(int i=0;i<n-1;i++) tmp[i]=sor2[i+1];
tmp[n-1]=sor2[0];
memcpy(sor2,tmp,sizeof(tmp));
}
void rotate3(){ //逆时针旋转
memset(tmp,0,sizeof(tmp));
for(int i=0;i<n;i++) tmp[i]=sor1[(i-tt%n+n)%n];
memcpy(sor1,tmp,sizeof(tmp));
}
signed main(){
cin>>n>>k>>t;
for(int i=0;i<k;i++) cin>>rot[i];
for(int i=0;i<n;i++) sor1[i]=sor2[i]=i;
tt=t;
rotate1(); //进行一次 R 操作 + 逆时针旋转一次，避免特判
rotate2();
for(int i=0;i<n;i++) jmp[sor2[i]][0]=i; //预处理 jmp 数组
for(int j=1;j<=40;j++) //递推 jmp 数组
for(int i=0;i<n;i++)
jmp[i][j]=jmp[jmp[i][j-1]][j-1];
for(int i=40;i>=0;i--){ //枚举 2^i
if((1ll<<i)<=t){
t-=(1ll<<i);
for(int j=0;j<n;j++) tmp[jmp[j][i]]=sor1[j]; //进行 2^i 次 S 操作
memcpy(sor1,tmp,sizeof(tmp));
}
}
rotate3(); //逆时针旋转 T 次
for(int i=0;i<n;i++) cout<<sor1[i]<<' ';
return 0;
}