快速矩阵乘法。注意,原始字符串即为decode后的字符串。题目是要找到原始串。
#include <cstdio>
#include <cstring> #define MAXN 85 typedef struct {
char m[MAXN][MAXN];
} mat_st; int n, m;
char buf[MAXN];
mat_st e; mat_st mat_mult(mat_st a, mat_st b) {
int i, j, k;
mat_st c;
memset(c.m, , sizeof(c.m)); for (i=; i<=n; ++i) {
for (j=; j<=n; ++j) {
for (k=; k<=n; ++k)
c.m[i][j] += a.m[i][k] & b.m[k][j];
}
}
return c;
} mat_st mat_power(mat_st a, int r) {
mat_st ret; memset(ret.m, , sizeof(ret.m));
for (int i=; i<=n; ++i)
ret.m[i][i] = ; while (r) {
if (r & )
ret = mat_mult(ret, a);
a = mat_mult(a, a);
r >>= ;
}
return ret;
} int main() {
mat_st org;
int i, j; while (scanf("%d %d",&n,&m)!=EOF && n) {
memset(org.m, , sizeof(org.m));
for (i=; i<=n; ++i) {
scanf("%d", &j);
org.m[i][j] = ;
}
getchar();
gets(buf+);
mat_st ans = mat_power(org, m);
for (i=; i<=n; ++i) {
for (j=; j<=n; ++j) {
if (ans.m[j][i]) {
printf("%c", buf[j]);
break;
}
}
}
printf("\n");
} return ;
}