题目描述：
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<stdio.h>
#include<cstdio>
#include<math.h>
#include<string.h>
#define M 9973
#define H 102
using namespace std;
typedef struct Matrix{
    int v[H][H];
} matrix;
//Matrix E;
//Matrix Ans;
Matrix Mul(Matrix aa,Matrix bb,int n){
//  cout<<"get in now"<<endl;
    Matrix cc;
    memset(cc.v,0,sizeof(cc.v));  //将所有的v置0
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int c=0;c<n;c++){
                cc.v[i][j]+=aa.v[i][c]*bb.v[c][j];
                cc.v[i][j]%=M;
            }
        }
    }
    return cc;
} 
 
Matrix pow(Matrix E,int k,int n){  //求x^y  x可能是longlong  E(n)^k 910^9==10^10 <21亿
    Matrix Ans;
    memset(Ans.v,0,sizeof(Ans.v));
    for(int i=0;i<n;i++){
                Ans.v[i][i]=1;
    }
    while(k!=0){
        if(k%2==1){
            Ans=Mul(E,Ans,n);
        }
        k/=2;
        E=Mul(E,E,n);
    }
    return Ans;
}
 
int main(){
    int t,n;
    int k;
    Matrix E;
    Matrix Ans;
    cin>>t;
        for(int j=0;j<t;j++){
            cin>>n>>k;
                    for(int a=0;a<n;a++){
                        for(int b=0;b<n;b++){
                            cin>>E.v[a][b];
                            E.v[a][b]%=M;
                        }
                    }
                    //矩阵输入完毕；
                     
                    Ans=pow(E,k,n);
                    int count=0;
                    for(int p=0;p<n;p++){
                        count=count + Ans.v[p][p];
                        count%=M;
                    }
                    cout<<count<<endl;
                 
            }
    return 0;
}
/**************************************************************
    Problem: 1443
    User: WZDCJ0206
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:1688 kb
****************************************************************/