【POJ】1026.Cipher

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题解

置换群的快速幂，然而我姿势水平不高，样例过不去，然后才明白这个置换的意思是这个位置上的数代表要把原位置的某个数换过来

需要新开一个数组存结果

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <ctime>
#include <map>
#include <algorithm>
#include <cmath>
#define MAXN 100005
#define eps 1e-8
//#define ivorysi
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int64;
typedef double db;int N,a[MAXN],L,ans[MAXN],t[MAXN],K,tmp[MAXN];
char str[MAXN],s[MAXN];
void mul(int *c,int *d) {
for(int i = 1 ; i <= N ; ++i) tmp[i] = c[d[i]];
for(int i = 1 ; i <= N ; ++i) c[i] = tmp[i];
}
void fpow(int c) {
for(int i = 1 ; i <= N ; ++i) t[i] = a[i];
for(int i = 1 ; i <= N ; ++i) ans[i] = i;
while(c) {
if(c & 1) mul(ans,t);
mul(t,t);
c >>= 1;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
while(scanf("%d",&N) != EOF && N) {
for(int i = 1 ; i <= N ; ++i) {
scanf("%d",&a[i]);
}
while(scanf("%d",&K) != EOF && K){
for(int i = 1 ; i <= N ; ++i) str[i] = ' ';
getchar();
gets(str + 1);
L = strlen(str + 1);
for(int i = 1 ; i <= N ; ++i) {
if(str[i] == 0) str[i] = ' ';
}
fpow(K);
for(int i = 1 ; i <= N ; ++i) {
s[ans[i]] = str[i];
}
for(int i = 1 ; i <= N ; ++i) putchar(s[i]);
putchar('\n');
}
putchar('\n');
}
return 0;
}