poj 1026(置换群)

题意：给你一个变换规则，和一个字符串，问经过k次变换后得到的字符串。

思路：开始的时候试图去找它的整个周期，谁知道周期太大了，各种RE，后来在得知此题需要用置换群来优化，第一次接触置换群学习了下！

代码实现：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
int a[205];
char str[205];
vector<int>Q[205];
int visited[205];
int n,k,num;

void zhouqi()
{
    int i,x;
    num=0;
    memset(visited,0,sizeof(visited));
    for(i=1;i<=n;i++)
     Q[i].clear();
    for(i=1;i<=n;i++)
    {
        if(visited[i]==0)
        {
            ++num;
            Q[num].push_back(i);
            visited[i]=1;
            x=a[i];
            while(i!=x)
            {
                visited[x]=1;
                Q[num].push_back(x);
                x=a[x];
            }
        }
    }
}

void change()
{
    int i,len;
    len=strlen(str+1);
    for(i=len+1;i<=n;i++)
     str[i]=' ';
    str[n+1]='';
}

void solve()
{
    int i,j,T;
    char res[205];
    for(i=1;i<=num;i++)
    {
       T=Q[i].size();
       for(j=0;j<T;j++)
           res[Q[i][(j+k)%T]]=str[Q[i][j]];
    }
    res[n+1]='';
    printf("%s
",res+1);
}

int main()
{
    int i;
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(i=1;i<=n;i++)
         scanf("%d",&a[i]);
        zhouqi();
        while(scanf("%d",&k)!=EOF&&k)
        {
            getchar();
            gets(str+1);
            change();
            solve(); 
        }
        printf("
");
    }
    return 0;
}