矩阵快速幂模板

#include<bits/stdc++.h>using namespace std;const int N = 12;const int Mod = 9973;int n;struct Mat{    int mat[N][N];};Mat operator *(Mat a, Mat b){    Mat c;    memset(c.mat, 0, sizeof(c.mat));    for(int k = 0; k < n; ++k)        for(int i = 0; i < n; ++i)            if(a.mat[i][k])                for(int j = 0; j < n; ++j)                    if(b.mat[k][j])                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;    return c;}Mat operator ^(Mat a, int k){    Mat c;    memset(c.mat,0,sizeof(c.mat));    for(int i = 0; i < n; ++i)        c.mat[i][i]=1;    for(; k; k >>= 1)    {        if(k&1) c = c*a;        a = a*a;    }    return c;}int main(){//    freopen("Input.txt","r",stdin);    int t,k;    scanf("%d",&t);    while(t--)    {        Mat a;        scanf("%d%d",&n,&k);        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)                scanf("%d",&a.mat[i][j]);        a=a^k;        int ans=0;        for(int i=0;i<10;i++)            ans=(ans+a.mat[i][i])%Mod;        printf("%d\n",ans);    }    return 0;}