hdoj 1575 Tr A

点击打开链接

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

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

代码：

//定义一个矩阵类，然后重载*，计算矩阵的快速幂（对于乘法和加法计算过程取模不影响结果）
#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);
    }
}