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;
}
补充:软件开发 , C++ ,