首页 > ACM题库 > HDU-杭电 > hdu 2371 Decode the Strings-快速幂-[解题报告]C++
2014
01-05

hdu 2371 Decode the Strings-快速幂-[解题报告]C++

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;
}

解题转自:http://blog.csdn.net/xingyeyongheng/article/details/9855103


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

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

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

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

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