题目：
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 Description
A为一个方阵，则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
22 21 00 13 999999991 2 34 5 67 8 9
Sample Output
22686
Author
xhd
Source
HDU 2007-1 Programming Contest
Recommend
linle
题目分析：
矩阵快速幂。
以下说一下为什么会存在快速幂这个方法(纯属个人理解,可能不太准确)。
我们经常会遇到这样的一个需求:"求a的b次幂模k"。当a和b都很大的时候，那么普通方法所得结果很可能已经超过了C/C++中整数所能表示的范围。这时候，我们就得利用一下矩阵快速幂了。
对于数字而言的快速幂的模板如下：
// m^n % kint 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 <iostream>#include <cstdio>#include <cstring>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;}
谁的指间滑过了千年时光；谁在反反复复中追问可曾遗忘；
