題意:給出一個編碼的順序,每經過一次編碼第i位上的字元回到第a[i]位上。然後給出一個k,和初始的串,問編碼k次後的串是什麼。
k可能會很大,不能暴力,是以要用置換群,找出輪換的環,假設環中有m個數,那麼每編碼m次,就代表這又回到了初始狀态,可以用k%m,這樣減少編碼的次數。如果在記錄輪換的位置,那麼對于輪換中的第i個字元編碼k次,就變成了輪換中的第(i+k)%m個字元。這樣直接可以計算出最終的結果。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;
int a[210],vis[210];
int num;
vector<int> v[210];
char s[2010];
char ans[210];
void group(int n)
{
memset(vis,0,sizeof vis);
for(int i=0,j;i<n;i++)
{
if(vis[a[i]]) continue;
j=i;
while(!vis[a[j]])
{
vis[a[j]]=1;
v[num].push_back(j);
j=a[j];
}
num++;
}
}
int main()
{
int n,k;
while(scanf("%d",&n)&&n)
{
num=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i]--;
}
for(int i=0;i<n;i++) v[i].clear();
group(n);
while(scanf("%d",&k)&&k)
{
getchar();
gets(s);
if(strlen(s)<n)
{
int l=strlen(s);
for(int i=l;i<n;i++) s[i]=' ';
}
for(int i=0;i<num;i++)
{
int len=v[i].size();
for(int j=0;j<len;j++)
{
ans[v[i][(j+k)%len]]=s[v[i][j]];
}
}
ans[n]='\0';
printf("%s\n",ans);
}
printf("\n");
}
return 0;
}