学步园

模版题，赤裸裸。

code：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 11;

int n,k;

struct Matrix
{
    int mat[MAXN][MAXN];
}E,A;

void init()
{
    int i,j;
    for(i=1;i<=10;i++)
    {
        for(j=1;j<=10;j++)
        {
            E.mat[i][j] = (i==j);
        }
    }
}

Matrix operator * (const Matrix a,const Matrix b)
{
    Matrix res;
    int i,j,k;
    for(i=1;i<=n;i++)
    {

        for(j=1;j<=n;j++)
        {
            res.mat[i][j]=0;
            for(k=1;k<=n;k++)
            {
                res.mat[i][j]= (res.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % 9973;
            }
        }
    }
    return res;
}

Matrix operator ^ (const Matrix a,int exp)
{
    Matrix res=E;
    Matrix tmp=a;
    while(exp)
    {
        if(exp&1)
            res = res * tmp;
        exp>>=1;
        tmp = tmp * tmp;
    }
    return res;
}

void solve()
{
    Matrix tmp = A ^ k;
    int ans=0;
    int i;
    for(i=1;i<=n;i++)
    {
        ans = (ans + tmp.mat[i][i] ) %9973;
    }
    printf("%d\n",ans);
}

int main()
{
    int i,j,cas;
    init();
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&A.mat[i][j]);
            }
        }
        solve();
    }
	return 0;
}