題意：
? ? ? 給你一個字符串，然后讓你執(zhí)行m次操作，每次操作把當(dāng)前的字符串映射到他給你的位置序列的位置，比如給的是 3 1 2，第一步就是把原來的3的位置的字母變到1的位置，1的變到2的位置，2的變到3，就這樣一直變換m次，最后給你一個變換完之后的，讓你求原始的（原題這個地方?jīng)]有敘述的很清楚）。

思路：
? ? ? 首先這種位置映射，或者是變換的很多都可以根據(jù)矩陣乘法來解決，這個題目的是個很簡單的應(yīng)用，比如我們要把1 2 3 4 5映射到 2 3 1 5 4的位置：

0 1 0 0 0 ? ? 1
0 0 1 0 0 ? ? 2
1 0 0 0 0 ?* ?3?
0 0 0 0 1 ? ? 4
0 0 0 1 0 ? ? 5 (這個是正向，題目是要求原始的，直接把n*n的矩陣變成自己的逆矩陣）

? ? 這樣就ok了，映射幾次就乘幾個前面的那個n*n的矩陣就行了，矩陣乘法有結(jié)合律，所以可以矩陣快速冪去求，矩陣乘法的三重for循環(huán)本身也有優(yōu)化（這個題目不優(yōu)化也能過），還有就是，一開始就說了，這個題目是要求原始的字符串，所以是不停的往回除，矩陣除法可以轉(zhuǎn)換成乘以要除的那個矩陣的逆矩陣，所以還是矩陣乘法。

#include<stdio.h> #include<string.h>#define N 80 + 3 typedef struct {int mat[N][N]; }A;A mat_mat(A a ,A b ,int n) {A c;memset(c.mat ,0 ,sizeof(c.mat));for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)if(a.mat[i][k])for(int j = 1 ;j <= n ;j ++)c.mat[i][j] += a.mat[i][k] * b.mat[k][j];return c; }A q_mat(A a ,int b ,int n) {A c;memset(c.mat ,0 ,sizeof(c.mat));for(int i = 1 ;i <= n ;i ++)c.mat[i][i] = 1;while(b){if(b&1) c = mat_mat(c ,a ,n);a = mat_mat(a ,a ,n);b /= 2;}return c; }int main () {char str[N];int num[N] ,i ,n ,m;A a;while(~scanf("%d %d" ,&n ,&m) && n + m){memset(a.mat ,0 ,sizeof(a.mat));for(i = 1 ;i <= n ;i ++){scanf("%d" ,&num[i]);a.mat[num[i]][i] = 1;} getchar();gets(str);a = q_mat(a ,m ,n);for(i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= n ;j ++)if(a.mat[i][j]) num[i] = j;for(i = 1 ;i <= n ;i ++)printf("%c" ,str[num[i] - 1]);puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu2371 矩阵乘法（求序列位置改变m次后的序列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。