hdu1575 Tr A 矩阵初识

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

Sample Output

2

2686

一面赶期中考，一面刷水题，QwQ，感觉第一次大学考试药丸辣。。。

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int maxn=;

int n;

struct mat

{

     int  m[maxn][maxn];

     mat(){memset(m,,sizeof(m));};

     mat friend operator*(mat a,mat b){

         mat d;

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

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

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

            d.m[i][j]=(d.m[i][j]+a.m[i][k]*b.m[k][j]%)%;

        return d;

     }

};

mat pow(mat x,int cnt){

    mat d;

    for(int i=;i<n;i++) d.m[i][i]=;

    while(cnt){

        if(cnt&) d=d*x;

        x=x*x;

        cnt>>=;

    }

    return d;

}

int main()

{

    int i,j,k,num,T;

    scanf("%d",&T);

    while(T--){

        mat ans;

        scanf("%d%d",&n,&k);

        num=;

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

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

         scanf("%d",&ans.m[i][j]);

        ans=pow(ans,k);

        for(i=;i<n;i++) num+=ans.m[i][i];

        printf("%d\n",num%);

    }

    return ;

}

秒客网

hdu1575 Tr A 矩阵初识

相关文章