hdoj 1575 Tr A

题目意思：给定一个n阶的方阵A，求A的K次方矩阵主对角线的和模9973的值。

解题思路：矩阵的快速幂，我么可以写一个矩阵类，然后写几个相应的函数，比如重载* 等，就可以像整数一样直接计算非常方便。

代码：
[cpp] 
//定义一个矩阵类，然后重载*，计算矩阵的快速幂（对于乘法和加法计算过程取模不影响结果） 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <string> 
#include <queue> 
using namespace std; 
const long long MAXN = 15; 
 
class Matrix { 
public: 
     long long m[MAXN][MAXN]; 
    Matrix(){} 
    //初始化 
    void init(long long  num[MAXN][MAXN]){ 
        for(int i = 0 ; i < MAXN ; i++){ 
            for(int j = 0 ; j < MAXN ; j++){ 
                m[i][j] = num[i][j]; 
            } 
        } 
    } 
    //求和函数 
    long long Sum(Matrix &M){ 
        long long sum = 0; 
        for(int i = 0 ; i < MAXN ; i++){ 
            for(int j = 0 ; j < MAXN ; j++){ 
                if(i == j) 
                   sum += M.m[i][j] % 9973;//记住每一步都取模 
                sum %= 9973; 
            } 
         } 
        return sum; 
    } 
    //重载矩阵的乘法运算 
    friend Matrix operator*(Matrix &m1 ,Matrix &m2) { 
        int i, j, k; 
        Matrix temp; 
        for (i = 0; i < MAXN; i++) { 
            for (j = 0; j < MAXN; j++) { 
                temp.m[i][j] = 0; 
                for(k = 0 ; k < MAXN ; k++) 
                    temp.m[i][j] += (m1.m[i][k] * m2.m[k][j]) % 9973; 
                temp.m[i][j] %= 9973; 
            } 
        } 
        return temp; 
    } 
    //矩阵的快速幂 
    friend Matrix quickpow(Matrix &M , long long n){ 
        Matrix tempans;//tempans对于矩阵的快速幂必须为单位矩阵 
        //tempans的初始化 
        for(int i = 0 ; i < MAXN ; i++){ 
            for(int j = 0 ; j < MAXN ; j++){ 
                if(i == j) 
                    tempans.m[i][j] = 1; 
                else 
                    tempans.m[i][j] = 0; 
            } 
        } 
        //矩阵的快速幂 
        while(n){ 
            if(n & 1) 
                tempans = tempans * M; 
            n = n >> 1; 
            M = M * M; 
        } 
        return ans; 
    } 
}; 
 
int main() { 
    Matrix A , ans; 
    long long T , n , k , sum;//数据类型为long long 就好 
    long long num[MAXN][MAXN];//输入的数据存入num数组 
    scanf("%lld" , &T); 
    while(T--){ 
        scanf("%lld%lld/n", &n , &k); 
        memset(num , 0 , sizeof(num)); 
        for(int i = 0 ; i < n ; i++){ 
            for(int j = 0 ; j < n ; j++) 
                scanf("%lld" , &num[i][j]); 
        } 
        A.init(num);//初始化A矩阵 
        ans = quickpow(A , k);//求出矩阵的快速幂 
        sum = ans.Sum(ans);//求出主对角线的和 
        printf("%d/n" , sum); 
    } 
} 

作者：cgl1079743846