链接：poj 1026

题意：给定n个大小1-n的不同的整数作为密钥，给定一个字符串，

求将该字符串经过k次编码后的字符串

分析：暴力求解会超时，可以利用置换群的知识解题

置换群：一个有限集合的一一变换叫做置换,一对对置换组成了置换群。

对于一个集合a(a[1],a[2],a[3]...a[n]) 通过置换可以变成

(b[a[1]],b[a[2]],b[a[3]]...b[a[n]])

b的作用就是置换(可以理解为某种函数的作用)，将原来的集合映射成具有

相应次序的集合a',a'可以看做是a的相同元素集合，不同的排列组合的一个集合

每个n元的置换都可以表示成若干个互不相交的循环置换的乘积，

设每个子循环置换的循环节为ci,则总的置换的循环节显然为lcm(c1,c2..cn)

#include
  
   
#include
   
     struct stu{ int num,period; }a[205]; int n; bool visit[205]; void cal_per() //求每个元素的周期 { int t,i; memset(visit,false,sizeof(visit)); for(i=1;i<=n;i++){ if(!visit[i]){ visit[i]=true; t=a[i].num; int cnt=1; while(t!=i){ visit[t]=true; cnt++; t=a[t].num; } a[i].period=cnt; t=a[i].num; while(t!=i){ a[t].period=cnt; t=a[t].num; } } } } int main() { char s[205],c,temp; int i,j,k,next; while(scanf("%d",&n)!=EOF){ if(n==0) break; for(i=1;i<=n;i++) scanf("%d",&a[i].num); cal_per(); while(scanf("%d",&k)&&k){ gets(s); for(i=strlen(s);i<=n;i++) s[i]=' '; s[n+1]=0; memset(visit,0,sizeof(visit)); for(i=1;i<=n;i++){ if(!visit[i]){ for(j=1;j<=k%a[i].period;j++){ c=s[a[i].num]; s[a[i].num]=s[i]; visit[i]=true; next=a[i].num; while(next!=i){ visit[next]=true; temp=s[a[next].num]; s[a[next].num]=c; c=temp; next=a[next].num; } } } } /*for(i=1;i<=n;i++) printf("%c",s[i]); printf("\n");*/ puts(s+1); } printf("\n"); } return 0; }