九度 题目1443：Tr A

九度 题目1443：Tr A

原题OJ链接：http://ac.jobdu.com/problem.php?pid=1443

题目描述：

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

输入：

数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

输出：

对应每组数据，输出Tr(A^k)%9973。

样例输入：

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

样例输出：

2
2686

解题思路：

矩阵快速幂，与二分求幂原理相同。

源代码：

#include<iostream>
#include<cstring>
using namespace std;
long long int A[15][15],B[15][15],C[15][15];
int T,n,k;

int main(){
    while(cin>>T){
        for(int t=1;t<=T;t++){
            cin>>n>>k;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    cin>>A[i][j];
                    B[i][j]=0;
                    if(i==j) B[i][j]=1;//B矩阵初始化为单位矩阵
                }
            }
            long long int ans=0; 
            while(k!=0){
                if(k%2==1){
                    for(int i=1;i<=n;i++){
                        for(int j=1;j<=n;j++){
                            ans=0;
                            for(int m=1;m<=n;m++){
                                ans=ans+A[i][m]*B[m][j]%9973;
                            }
                            C[i][j]=ans%9973;
                        }
                    }
                    for(int i=1;i<=n;i++){
                        for(int j=1;j<=n;j++){
                            B[i][j]=C[i][j];
                        }
                    }
                }
                k=k/2;
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        ans=0;
                        for(int m=1;m<=n;m++){
                            ans=ans+A[i][m]*A[m][j]%9973;
                        }
                        C[i][j]=ans%9973;
                    }
                }

                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        A[i][j]=C[i][j];
                    }
                }
            }
            ans=0;
            for(int i=1;i<=n;i++){
                ans=ans+B[i][i]%9973;
            }
            cout<<ans%9973<<endl;

        }
    }
    return 0;
}