杭电 2371 Decode the Strings

逃离我推掉我的手 2022-05-16 13:51 156阅读 0赞

题目链接：[点我][Link 1]  
Problem Description  
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?

Input  
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.

Output  
For each test case, print one line with the decoded string.

Sample Input  
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

Sample Output  
hello  
second test case  
encoded?

用矩阵交换字母顺序，线性代数的知识点  
要知道行列式的乘法规则  
![这里写图片描述][70]  
题目要我们逆推，求原矩阵的逆矩阵，详细实现见代码

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<map>
    #include<vector>
    #include<queue>
    #include<set>
    #include<iomanip>
    #include<cctype>
    using namespace std;
    #define ll long long
    #define edl putchar('\n')
    #define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define FOR(i,a,b) for(int i=a;i<=b;i++)
    #define ROF(i,a,b) for(int i=a;i>=b;i--)
    #define FORLL(i,a,b) for(ll i=a;i<=b;i++)
    #define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
    #define mst(a) memset(a,0,ssizeof(a))
    #define mstn(a,n) memset(a,n,ssizeof(a))
    #define zero(x)(((x)>0?(x):-(x))<eps)
    const int ssize=100;
    int n,m;
    int p[ssize],num[ssize];
    char s[ssize];
    struct Matrix {
    	int a[ssize][ssize];
    	Matrix() {
    		memset(a,0,sizeof(a));
    	}
    	void init() {
    		for(int i=0; i<n; i++)
    			for(int j=0; j<n; j++)
    				a[i][j]=(i==j);
    	}
    	Matrix operator + (const Matrix &B)const {
    		Matrix C;
    		for(int i=0; i<n; i++)
    			for(int j=0; j<n; j++)
    				C.a[i][j]=(a[i][j]+B.a[i][j]);
    		return C;
    	}
    	Matrix operator * (const Matrix &B)const {
    		Matrix C;
    		for(int i=0; i<n; i++)
    			for(int k=0; k<n; k++)
    				for(int j=0; j<n; j++)
    					C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j]);
    		return C;
    	}
    	Matrix operator ^ (const ll &t)const {
    		Matrix A=(*this),res;
    		res.init();
    		ll p=t;
    		while(p) {
    			if(p&1)res=res*A;
    			A=A*A;
    			p>>=1;
    		}
    		return res;
    	}
    
    };
    
    
    int main() {
    	int i;
    	Matrix origin,A,ans;
    	while(scanf("%d%d",&n,&m)!=EOF) {
    		if(n==0&&m==0)
    			break;
    		for(i=1; i<=n; i++)
    			scanf("%d",&num[i]);
    		for(i=1; i<=n; i++) //取原矩阵的逆矩阵 
    			p[num[i]]=i;
    		memset(origin.a,0,sizeof(origin.a));  
    		for(i=0; i<n; i++)
    			origin.a[i][p[i+1]-1]=1;
    		getchar();
    		gets(s);
    		
    		origin=origin^m;
    		memset(A.a,0,sizeof(A.a));  //原始序列[1 2 3 4 5 ...n]
    		for(i=0; i<n; i++)
    			A.a[i][0]=i;
    		ans=origin*A;  //与原始序列相乘
    		for(i=0; i<n; i++)
    			printf("%c",s[ans.a[i][0]]);
    		//  printf("%d ",ans.a[i][1]);
    		printf("\n");
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2371
[70]: /images/20220516/a4e10c987bbf446ba6c78d4f622dcb56.png