杭电 2371 Decode the Strings-蒲公英云

杭电 2371 Decode the Strings

题目链接：点我
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.

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).
Repeat the following step m times.
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?

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

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