(hdu step 8.3.1)Tr A(矩陣快速冪——求矩陣m的n次冪的跡%k的結果)

題目：

 

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

2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9

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;
}