矩阵快速幂

http://acm.hdu.edu.cn/showproblem.php?pid=1575

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=11,mod=9973;
int n,b;
struct Matrix
{
    int m[N][N];
}curr;
Matrix multi(Matrix a,Matrix b)
{
    Matrix ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return ans;
}
Matrix fast_pow(Matrix a,int b)
{
    Matrix ans,base=a;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans.m[i][j]=(i==j);
        }
    }
    while(b)
    {
        if(b&1)
        {
            ans=multi(ans,base);
        }
        base=multi(base,base);
        b>>=1;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&b);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&curr.m[i][j]);
            }
        }
        curr=fast_pow(curr,b);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            ans=(ans+curr.m[i][i])%mod;
        }
        printf("%d\n",ans%mod);
    }

}