POJ 1026 置换群的k次幂问题

题目大意：

给定了一组对应关系，经过k次幂后，得到新的对应关系b[i]，然后将给定的字符串上的第i位字符放置到b[i]的位置上，

如果字符串长度不足n就用空格补足，这里的是空格，也就是str[i] = ' ',不是str[i]='\0' ,自己这里错了好几回就是找不到问题，看了别人代码才明白

置换群的k次幂问题不清楚，可以看看<<置换群快速幂运算+研究与探讨.pdf>>

这里初始给定的置换群要注意这个群不一定是一个循环集，我们要先统计出它的每一个循环集，然后每一个分别进行操作计算

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int N = ;

 //qun[i]保存第i个循环集的第一个数，a[]表示原映射,b[]表示k次幂后得到的新的对应关系，cnt表示循环集的个数

 int a[N] , b[N] , tmp[N] , tmp_new[N] , qun[N] , vis[N] , cnt;

 char str[N];

 void circle(int u)

 {

     qun[cnt] = u;

     int v = u;

     while(u != a[v]){

         vis[v] = ;

         v = a[v];

     }

     vis[v] = ;

     cnt++;

 }

 //返回当前循环集的长度

 int get_tmp(int cnt)

 {

     int index = ;

     tmp[index++] = qun[cnt];

    // cout<<"here: "<<cnt<<" start: "<<qun[cnt]<<endl;

     int u = a[qun[cnt]];

     while(u != tmp[]){

         tmp[index++] = u;

         u = a[u];

     }

     return index;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int n , k;

     while(scanf("%d" , &n) , n)

     {

         for(int i= ; i<=n ; i++)

             scanf("%d" , a+i);

         memset(vis ,  ,sizeof(vis));

         cnt = ;

         //初始置换群中可能有多个循环集，我们需要一个一个循环集进行操作

         for(int i= ; i<=n ; i++)

             if(!vis[i]) circle(i);

         while(scanf("%d" , &k) , k){

             getchar();

             gets(str+);

             int len = strlen(str+);

             for(int i=len+ ; i<=n ; i++)

                 str[i] = ' ';

            // printf("%s\n" , str+1);

             for(int i= ; i<cnt ; i++){

                 int len = get_tmp(i);

                 int index =  , pos = ;

                 tmp_new[index++] = tmp[];

                 memset(vis ,  , sizeof(vis));

                 vis[] = ;

                 for(int i= ; i<len ; i++){

                     pos = (pos+k)%len;

                     //分裂成了一个小循环集

                     if(vis[pos]){

                         for(int i=; i<index ; i++){

                             if(i <index-) b[tmp_new[i]] = tmp_new[i+];

                             else b[tmp_new[i]] = tmp_new[];

                         }

                         //tmp数组下标清零

                         index = ;

                         pos = (pos+)%len;

                     }

                     tmp_new[index++] = tmp[pos];

                     vis[pos] = ;

                 }

                 //最后一个分裂出来的循环集的映射加入到b中

                 for(int i=; i<index ; i++){

                     if(i <index-) b[tmp_new[i]] = tmp_new[i+];

                     else b[tmp_new[i]] = tmp_new[];

                 }

             }

             char ans[N];

             for(int i= ; i<=n ; i++){

                 ans[b[i]] = str[i];

             }

             ans[n+] = '\0';

             printf("%s\n" , ans+);

         }

         puts("");

     }

     return ;

 }