本文共 2545 字，大约阅读时间需要 8 分钟。

题目链接

思路

题目条件很玄学，要找出值为$b_i$的元素与$1$位置的元素交换。
为了防止到处找元素，我们把每个元素在哪个位置记下来，记录$p_i$为值为$i$的元素的位置。
这样，题目就变成了：把$p$数组中的位置$b_i$的元素与值为$1$的元素交换（方便起见，把这样的交换记作$swap(b_i)$）。
现在，我们只要关心值为$1$的元素的位置。

我们研究研究对$p$数组交换的性质：

性质$1$：$swap(x)$后，$1$的位置变成了$x$。
证明：这个结论是很显然的，没有证明。

性质$1.5$：经过一连串的$swap(b_1),swap(b_2),\cdots,swap(b_q)$后，$1$的位置变成了$b_q$。
证明：由性质$1$得到。

性质$2$：如果经过一轮交换，$p$数组中$i$位置的值到了$s_i$上，若有$s_1=1$，那么现在再次进行同样的交换，这个值会到$s_{s_i}$上。
证明：交换的是位置，因此第一次交换后可以把这个数组视为原数组。

根据推论$1.5$和性质$2$，按照$b$数组的顺序，进行两轮交换后，可以根据性质$2$来快速计算后面的变换情况。
具体流程：

• 按照$b$数组的顺序进行两轮交换；
  • 计算出上面性质$2$中提到的$s$值；
  • 利用快速幂，计算出前$\lfloor \frac{n}{q}\rfloor$项的值；
  • 最后暴力计算出最后$n \mod q$项的值。

  • 代码

    #include <cstdio>#include <cstring>#include <algorithm>const int maxn=200000;int n,q;long long m;struct per{  int a[maxn+10];  per operator *(const per &other) const  {    per res;    for(register int i=1; i<=n; ++i)      {        res.a[i]=other.a[a[i]];      }    return res;  }};int a[maxn+10],b[maxn+10],p[maxn+10],opos,tmp[maxn+10];per now,res;int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int jump(int *ar,int t){  for(register int i=1; i<=t; ++i)    {      std::swap(ar[opos],ar[b[(i-1)%q+1]]);      opos=b[(i-1)%q+1];    }  return 0;}int main(){  n=read();  q=read();  scanf("%I64d",&m);  for(register int i=1; i<=n; ++i)    {      a[i]=read();    }  for(register int i=1; i<=q; ++i)    {      b[i]=read();    }  for(register int i=1; i<=n; ++i)    {      p[a[i]]=i;    }  opos=a[1];  if(m<=2*q)    {      jump(p,m);      for(register int i=1; i<=n; ++i)        {          tmp[p[i]]=i;        }      for(register int i=1; i<n; ++i)        {          printf("%d ",tmp[i]);        }      printf("%d\n",tmp[n]);      return 0;    }  jump(p,q);  memcpy(tmp,p,sizeof p);  jump(p,q);  for(register int i=1; i<=n; ++i)    {      now.a[tmp[i]]=p[i];    }  for(register int i=1; i<=n; ++i)    {      res.a[i]=i;    }  long long t=m/q-2;  while(t)    {      if(t&1)        {          res=res*now;        }      t>>=1;      now=now*now;    }  now=res;  for(register int i=1; i<=n; ++i)    {      p[i]=now.a[p[i]];    }  jump(p,m%q);  for(register int i=1; i<=n; ++i)    {      tmp[p[i]]=i;    }  for(register int i=1; i<n; ++i)    {      printf("%d ",tmp[i]);    }  printf("%d\n",tmp[n]);  return 0;}