题目：

Tr A

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 66 Accepted Submission(s): 57

Problem DescriptionA为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

Input数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

Output
对应每组数据，输出Tr(A^k)%9973。

Sample Input

Sample Output

2
2686

Authorxhd

SourceHDU 2007-1 Programming Contest

Recommendlinle

题目分析：

矩阵快速幂。

以下说一下为什么会存在快速幂这个方法(纯属个人理解,可能不太准确)。

我们经常会遇到这样的一个需求:"求a的b次幂模k"。当a和b都很大的时候，那么普通方法所得结果很可能已经超过了C/C++中整数所能表示的范围。这时候，我们就得利用一下矩阵快速幂了。

对于数字而言的快速幂的模板如下：

// m^n % k
int quickpow(int m,int n,int k)
{
    int b = 1;
    while (n > 0)
    {
          if (n & 1)
             b = (b*m)%k;
          n = n >> 1 ;
          m = (m*m)%k;
    }
    return b;
}

对于矩阵而言的快速幂的模板如下：

struct Mat {
   int  mat[N][N];
};

/**
 * 矩阵相乘.
 * 返回的是矩阵a*矩阵b候所得的结果
 */
Mat operator * (Mat a, Mat b) {
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(i = 0; i < n; ++i) {
        for(j = 0; j < n; ++j) {
            for(k = 0; k < n; ++k) {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }

            c.mat[i][j] %= 9973;//这个是根据题目加的,结果矩阵中每一个都应该%9973,否则可能会溢出
        }
    }
    return c;
}


/**
 * 求矩阵的幂次方
 * 返回的是a^k次幂
 */
Mat operator ^ (Mat a, int k) {
    Mat c;
    int i, j;
    for(i = 0; i < n; ++i){
        for(j = 0; j < n; ++j){
            c.mat[i][j] = (i == j);    //初始化为单位矩阵
        }
    }

    //快速幂算法
    for(; k; k >>= 1) {
        if(k&1){
        	c = c*a;
        }
        a = a*a;
    }
    return c;
}


/**
 * 求矩阵的迹.
 *
 * 其实就是把矩阵对角线上的数加一下即可
 *
 */
int getTr(Mat a,int n){
	int i;
	int sum = 0;
	for(i = 0 ; i < n ; ++i){
		sum += a.mat[i][i];//将矩阵对对角线上的数累加以下
		sum %= 9973;//防止数字溢出,每一个都取模
	}

	return sum;
}

代码如下：

/*
 * a.cpp
 *
 *  Created on: 2015年3月25日
 *      Author: Administrator
 */

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int N = 11; int n; struct Mat { int mat[N][N]; }; /** * 矩阵相乘. * 返回的是矩阵a*矩阵b候所得的结果 */ Mat operator * (Mat a, Mat b) { Mat c; memset(c.mat, 0, sizeof(c.mat)); int i, j, k; for(i = 0; i < n; ++i) { for(j = 0; j < n; ++j) { for(k = 0; k < n; ++k) { c.mat[i][j] += a.mat[i][k] * b.mat[k][j]; } c.mat[i][j] %= 9973;//这个是根据题目加的,结果矩阵中每一个都应该%9973,否则可能会溢出 } } return c; } /** * 求矩阵的幂次方 * 返回的是a^k次幂 */ Mat operator ^ (Mat a, int k) { Mat c; int i, j; for(i = 0; i < n; ++i){ for(j = 0; j < n; ++j){ c.mat[i][j] = (i == j); //初始化为单位矩阵 } } //快速幂算法 for(; k; k >>= 1) { if(k&1){ c = c*a; } a = a*a; } return c; } /** * 求矩阵的迹. * * 其实就是把矩阵对角线上的数加一下即可 * */ int getTr(Mat a,int n){ int i; int sum = 0; for(i = 0 ; i < n ; ++i){ sum += a.mat[i][i];//将矩阵对对角线上的数累加以下 sum %= 9973;//防止数字溢出,每一个都取模 } return sum; } int main(){ int t; scanf("%d",&t); while(t--){ int k; scanf("%d%d",&n,&k); Mat m; int i; int j; for(i = 0 ; i < n ; ++i){ for(j = 0 ; j < n ; ++j){ scanf("%d",&m.mat[i][j]); } } m = m^k;//这就是求矩阵k次幂的用法 printf("%d\n",getTr(m,n)); } return 0; }

(hdu step 8.3.1)Tr A(矩阵快速幂――求矩阵m的n次幂的迹%k的结果)

Tr A