bsp; a.mat[i][p[i]]=1;
}
getchar();
gets(str);
ans=quickMatPow(a,n,m);
ans=matMul(b,ans,n);
for (i=1;i<=n;i++)
printf("%c",str[ans.mat[1][i]-1]);
printf("\n");
}
return 0;
}
将此源程序提交给HDU 2371 “Decode the Strings”，可以Accepted。
【例2】送给圣诞夜的礼品。
已知序列1,2,3,…,n，给出m个置换操作， 例如某个置换操作 6 1 3 7 5 2 4，表示把6位置上的元素换到1位置上，1位置上的元素换到2位置上…。
求原序列为1,2,3,……,n的序列按给出的m个置换操作的顺序进行k次置换后得到的新序列。若k>m，则第m+1次置换操作做第1个置换操作，第m+2次置换操作做第2个置换操作，…。
数据说明： 1<=n<=100；1<=m<=10；1<=k<=2^31-1。
本题完整的描述可以参看 https://vijos.org/p/1049。
（1）编程思路。
搞懂了例1，本题就容易入手了。m 个置换操作需要构造m个置换矩阵。
构造好置换矩阵后，先将m个置换矩阵乘起来，得到ans矩阵，则此时的ans矩阵相当进行了m次操作；再将ans矩阵进行k/m次幂，此时相当进行了k次操作。当然，由于k不一定整除m，因此还需按m个置换操作的顺序进行k%m次的置换操作。
（2）源程序。
#include <stdio.h>
#include <string.h>
struct Matrix
{
int mat[101][101]; // 存储矩阵中各元素
};
Matrix p[11];
Matrix matMul(Matrix a ,Matrix b,int n)
{
Matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) ;
return c;
}
Matrix quickMatPow(Matrix a ,int n,int b) // n阶矩阵a快速b次幂
{
Matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matMul(c ,a ,n); // c=c*a;
a = matMul(a ,a ,n); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int n,m,k,i,j,num,a[101];
Matrix ans;
scanf("%d%d%d",&n,&m,&k);
for (i=0;i<m;i++)
{
memset(p[i].mat,0,sizeof(p[i].mat));
for (j=1;j<=n;j++)
{
scanf("%d",&num);
p[i].mat[j][num]=1; // 构造的置换矩阵
&nbs