题解 UVA306 【Cipher】

题目相当于是求一个串按某种指定方式换位多次后形成的串。

因为 \(k\) 很大，所以不能直接模拟。

我们考虑样例，对于一个以 4 5 3 7 2 8 1 6 10 9 为标准的转移，我们若转移两次，就相当于进行一次以 7 5 3 1 2 8 4 6 10 为标准的转移，并且每次换的方式是固定的，所以满足结合律，可以用快速幂来解决。

时间复杂度为 \(O(nlogk)\)

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int a[M],b[M],ans[M],d[M];
char s[M];
int n,k;
void solve1(){
	for(int i=1;i<=n;i++){
		a[i]=ans[i];
	}
	for(int i=1;i<=n;i++){
		ans[b[i]]=a[i];
	}
}
void solve2(){
	for(int i=1;i<=n;i++){
		a[i]=b[i];
	}
	for(int i=1;i<=n;i++){
		b[i]=a[b[i]];
	}
}
int main(){
	while(1){
		scanf("%d",&n);
		if(!n) return 0;
		for(int i=1;i<=n;i++){
			scanf("%d",&d[i]);
		}
		while(1){
			scanf("%d",&k);
			getchar();
			if(!k) break;
			for(int i=1;i<=n;i++){
				ans[i]=i;
				b[i]=d[i];
			}
			int len=0;	
			while((s[++len]=getchar())!=‘\n‘);
			len--;
			if(len<n){
				for(++len;len<=n;++len){
					s[len]=‘ ‘;
				}
			}
			while(k){
				if(k&1){
					solve1();
				}
				solve2();
				k>>=1;
			}
			for(int i=1;i<=n;i++){
				printf("%c",s[ans[i]]);
			}
			printf("\n");
		} 
		printf("\n");
	}
	return 0;
} 

题解 UVA306 【Cipher】

原文：https://www.cnblogs.com/yzk-home/p/14249562.html