poj 1026(置换群)

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

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

代码实现：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<vector>

using namespace std;

int a[];

char str[];

vector<int>Q[];

int visited[];

int n,k,num;

void zhouqi()

{

    int i,x;

    num=;

    memset(visited,,sizeof(visited));

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

     Q[i].clear();

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

    {

        if(visited[i]==)

        {

            ++num;

            Q[num].push_back(i);

            visited[i]=;

            x=a[i];

            while(i!=x)

            {

                visited[x]=;

                Q[num].push_back(x);

                x=a[x];

            }

        }

    }

}

void change()

{

    int i,len;

    len=strlen(str+);

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

     str[i]=' ';

    str[n+]='\0';

}

void solve()

{

    int i,j,T;

    char res[];

    for(i=;i<=num;i++)

    {

       T=Q[i].size();

       for(j=;j<T;j++)

           res[Q[i][(j+k)%T]]=str[Q[i][j]];

    }

    res[n+]='\0';

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

}

int main()

{

    int i;

    while(scanf("%d",&n)!=EOF&&n)

    {

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

         scanf("%d",&a[i]);

        zhouqi();

        while(scanf("%d",&k)!=EOF&&k)

        {

            getchar();

            gets(str+);

            change();

            solve();

        }

        printf("\n");

    }

    return ;

}