hdu1575 Tr A 矩阵快速幂模板题

hdu1575   TrA

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1575

都不需要构造矩阵，矩阵是题目给的，直接套模板，把对角线上的数相加就好了，记得取膜就好了。

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define maxn 12

#define MOD 9973

using namespace std;

typedef long long ll;

ll n,k;

struct Matrix{

    ll mat[][];

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

        for(int i=;i<n;i++)

            for(int j=;j<n;j++){

                tmp.mat[i][j]=;

                for(int k=;k<n;k++){

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;

                    tmp.mat[i][j]%=MOD;

                }

            }

        return tmp;

    }

};

ll POW(Matrix &m,int k){

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

    for(int i=;i<n;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    ll sum=;

    for(int i=;i<n;i++){

        sum+=ans.mat[i][i];

        sum%=MOD;

    }

    return sum;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    int T;

    cin>>T;

   while(T--){

      cin>>n>>k;

      Matrix m;

      for(int i=;i<n;i++)

          for(int j=;j<n;j++) cin>>m.mat[i][j];

      cout<<POW(m,k)<<endl;

   }

    return ;

}