poj 1026 Cipher (置換群)

poj 1026 Cipher (置換群)

鏈接：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;
}