HDU 1575 Tr A

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1575

 

 

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2597    Accepted Submission(s): 1934

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

2

2 2

1 0

0 1

3 99999999

1 2 3

4 5 6

7 8 9

 

 

Sample Output

2

2686

 

 

Author

 

xhd

 

 

Source

 

HDU 2007-1 Programming Contest

 

分析：这道题目可以用矩阵快速幂的方式来求答案。关于快速幂，如果不懂的童鞋可以看看我在博客上写的HDU 2035 人见人爱的A^B 这道题，关于普通数字大幂运算的算法，对于矩阵我们只要重载下矩阵运算的操作符就可以。

矩阵的乘法是，m[i][j] =  A[i][1]*B[1][j]+A[i][2]*B[2][j]+.....A[i][j]*B[i][j];

那么我们在矩阵这个结构体内重载下运算符

struct Matrix{
    int mat[N][N];
    Matrix operator *(const Matrix m)const{
        //用来存储运算完成之后的矩阵
        Matrix temp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //初始化答案矩阵
                temp.mat[i][j]=0;
                for(int k=0;k<n;k++){
                   //按照矩阵乘法模拟运算
                    temp.mat[i][j] += this->mat[i][k]*m.mat[k][j]%MOD;
                    temp.mat[i][j]%=MOD;
                }
            }
        }
        return temp;
    }
};

之后就和数字的大幂运算一样了

        Matrix ret;
        memset(ret.mat,0,sizeof(ret.mat));
        for(int i=0;i<n;i++)
            ret.mat[i][i] = 1;
        while(k)
        {
            if(k&1)ret = ret * mt;
            mt = mt*mt;
            k>>=1;
        }

 最后答案只要统计累加答案矩阵对角线上的数字就可以，注意每步取模。

 

完整代码：

#include<cstdio>
#include<cstring>
#define MOD 9973
int t,n,k;
struct Matrix{
    int mat[10][10];
    Matrix operator *(const Matrix m)const{
        Matrix temp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                temp.mat[i][j]=0;
                for(int k=0;k<n;k++){
                    temp.mat[i][j] += this->mat[i][k]*m.mat[k][j]%MOD;
                    temp.mat[i][j]%=MOD;
                }
            }
        }
        return temp;
    }
};
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        Matrix mt;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&mt.mat[i][j]);
            }
        }
        Matrix ret;
        memset(ret.mat,0,sizeof(ret.mat));
        for(int i=0;i<n;i++)
            ret.mat[i][i] = 1;
        while(k)
        {
            if(k&1)ret = ret * mt;
            mt = mt*mt;
            k>>=1;
        }
        int ans = 0;
        for(int i=0;i<n;i++)
            ans = (ans + ret.mat[i][i])%MOD;
        printf("%d\n",ans);

    }
}