【HDU1575】Tr A

题目链接

Tr A

题目描述

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

输入格式

数据的第一行是一个(T)，表示有(T)组数据。
每组数据的第一行有(n)((2 le n le 10))和(k)((2 le 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

题解

题目要求矩阵(A)的(k)次方的迹。
迹就是矩阵左上角到右下角的那条对角线。
直接用矩阵快速幂做就好了。
不会矩阵快速幂的可以看这一篇文章
上代码：

#include<bits/stdc++.h>
#define mod 9973
using namespace std;
int t;
int n,k;
struct aa{
    int a[19][19];
}a;
aa cc(aa x,aa y){
    aa ans;
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n;i++){
            ans.a[j][i]=0;
            for(int o=1;o<=n;o++){
                ans.a[j][i]+=x.a[j][o]*y.a[o][i];
                ans.a[j][i]%=mod;
            }
        }
    }
    return ans;
}
aa ksm(aa x,int p){
    aa ans;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            ans.a[j][i]=(j==i);
    while(p){
        if(p&1) ans=cc(ans,x);
        x=cc(x,x);
        p>>=1;
    }
    return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int j=1;j<=n;j++)
            for( int i=1;i<=n;i++)
                scanf("%d",&a.a[j][i]);
        aa ans=ksm(a,k);
        int anss=0;
        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++)
                if(j==i ) anss=(anss+ans.a[j][i])%mod;
        printf("%d
",anss);
    }
    return 0;
}