cipher(置换群，找循环节).cpp

杭电acm解题报告2001---2099.

//可用置换群幂运算加速
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n,k;
int ex[210], last[210], seq[210];
char txt[210];
bool vis[210];

void find_circle()
{
	int i,j;
	int cir[210];
	memset(vis,0,sizeof(vis));
	for(i=0;i<n;i++) {
		if(!vis[i]) {
			int tpos = i;
			int len = 0;
			do {
				cir[len] = tpos;
				vis[tpos] = true;
				tpos = ex[ tpos ];
				len ++;
			} while(tpos != i);
			for(j=0;j<len;j++) {
				last[ cir[j] ] = cir[ (j+k)%len ];
				seq[ cir[ (j+k)%len ] ] = cir[j];
			}
		}
	}
}

int main()
{
	int i;
	while(scanf("%d", &n), n) {
		for(i=0;i<n;i++) {
			scanf("%d", ex+i);
			ex[i] --;
		}
		while(scanf("%d", &k), k) {
			getchar();
			gets(txt);
			int len = strlen(txt);
			while(len < n) {
				txt[len ++] = ' ';
			}
			txt[len] = 0;
			find_circle();
			for(i=0;i<n;i++) {
				putchar(txt[ seq[i] ]);
			}
			printf("\n");
		}
		printf("\n");
	}
}