HDOJ - 2371 矩陣乘法

   構造轉換矩陣...如.2 3 1 5 4..構造成
     0 0 1 0 0
     1 0 0 0 0
     0 1 0 0 0
     0 0 0 0 1
     0 0 0 1 0
     將 (1,2,3,4,5)與這個矩陣相乘能變成(2,3,1,5,4)
    
Program:
[cpp] 
#include<iostream> 
#include<stdio.h> 
#include<algorithm> 
#include<string.h> 
#include<math.h> 
#include<map> 
#include<queue> 
#include<stack> 
#include<set> 
#define ll long long 
#define oo 2000000000 
#define pi acos(-1)   
using namespace std; 
struct node 
{ 
    int s[85][85]; 
}h,_2jie[32]; 
int n,m; 
char s[85],ans[85]; 
node mul(node a,node b) 
{ 
    int k,i,j; 
    node h; 
    memset(h.s,0,sizeof(h.s)); 
    for (k=1;k<=n;k++) 
       for (i=1;i<=n;i++) 
          for (j=1;j<=n;j++) 
             h.s[i][j]+=a.s[i][k]*b.s[k][j]; 
    return h; 
} 
node GetMatrix(int m) 
{ 
    int i;  
    _2jie[0]=h; 
    for (i=1;i<=30;i++) _2jie[i]=mul(_2jie[i-1],_2jie[i-1]); 
    memset(h.s,0,sizeof(h.s)); 
    for (i=1;i<=n;i++) h.s[i][i]=1; 
    for (i=0;i<=30;i++) 
       if (m & (1<<i)) 
          h=mul(h,_2jie[i]); 
    return h; 
} 
int main() 
{   
    int i,x,t[85]; 
    while (~scanf("%d%d",&n,&m)) 
    { 
            if (!n && !m) break; 
            memset(h.s,0,sizeof(h.s)); 
            for (i=1;i<=n;i++) 
            { 
                   scanf("%d",&x); 
                   h.s[i][x]=1; 
            } 
            h=GetMatrix(m); 
            for (i=1;i<=n;i++) 
              for (x=1;x<=n;x++) 
                if (h.s[i][x]==1) 
                   t[x]=i;  
            gets(s+1); 
            gets(s+1); 
            for (i=1;i<=n;i++) ans[i]=s[t[i]]; 
            ans[n+1]='\0'; 
            puts(ans+1); 
    } 
    return 0; 
}