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