2014
01-05

# Decode the Strings

Bruce Force has had an interesting idea how to encode strings. The following is the description of how the encoding is done:

Let x1,x2,…,xn be the sequence of characters of the string to be encoded.

1. Choose an integer m and n pairwise distinct numbers p1,p2,…,pn from the set {1, 2, …, n} (a permutation of the numbers 1 to n).
2. Repeat the following step m times.
3. For 1 ≤ i ≤ n set yi to xpi, and then for 1 ≤ i ≤ n replace xi by yi.

For example, when we want to encode the string "hello", and we choose the value m = 3 and the permutation 2, 3, 1, 5, 4, the data would be encoded in 3 steps: "hello" -> "elhol" -> "lhelo" -> "helol".

Bruce gives you the encoded strings, and the numbers m and p1, …, pn used to encode these strings. He claims that because he used huge numbers m for encoding, you will need a lot of time to decode the strings. Can you disprove this claim by quickly decoding the strings?

The input contains several test cases. Each test case starts with a line containing two numbers n and m (1 ≤ n ≤ 80, 1 ≤ m ≤ 109). The following line consists of n pairwise different numbers p1,…,pn (1 ≤ pi ≤ n). The third line of each test case consists of exactly n characters, and represent the encoded string. The last test case is followed by a line containing two zeros.

The input contains several test cases. Each test case starts with a line containing two numbers n and m (1 ≤ n ≤ 80, 1 ≤ m ≤ 109). The following line consists of n pairwise different numbers p1,…,pn (1 ≤ pi ≤ n). The third line of each test case consists of exactly n characters, and represent the encoded string. The last test case is followed by a line containing two zeros.

5 3
2 3 1 5 4
helol
16 804289384
13 10 2 7 8 1 16 12 15 6 5 14 3 4 11 9
scssoet tcaede n
8 12
5 3 4 2 1 8 6 7
encoded?
0 0

hello
second test case
encoded?

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=80+10;
int array[MAX][MAX],sum[MAX][MAX];
char s[MAX];
int n,m,a;

void MatrixMult(int a[MAX][MAX],int b[MAX][MAX]){
int c[MAX][MAX]={0};
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
c[i][j]+=a[i][k]*b[k][j];
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)a[i][j]=c[i][j];
}
}

void MatrixPow(int k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
sum[i][j]=(i == j);
}
}
while(k){
if(k&1)MatrixMult(sum,array);
MatrixMult(array,array);
k>>=1;
}
}

int main(){
while(cin>>n>>m,n+m){
memset(array,0,sizeof array);
for(int i=0;i<n;++i){
cin>>a;
array[a-1][i]=1;//初始矩阵
}
getchar();
gets(s);
MatrixPow(m);//置换m次
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(sum[i][j]){printf("%c",s[j]);break;}
}
}
cout<<endl;
}
return 0;
}

1. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

2. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

3. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！