题目地址：HDU 1575

矩阵高速幂裸题。

初学矩阵高速幂。曾经学过高速幂。今天一看矩阵高速幂，原来其原理是一样的，这就好办多了。都是利用二分的思想不断的乘。仅仅只是把数字变成了矩阵而已。

代码例如以下:

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

const int mod=9973;

int n;

struct matrix

{

    int ma[20][20];

}init, res;

matrix Mult(matrix x, matrix y)

{

    matrix tmp;

    int i, j, k;

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

    {

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

        {

            tmp.ma[i][j]=0;

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

            {

                tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod;

            }

        }

    }

    return tmp;

}

matrix Pow(matrix x, int k)

{

    matrix tmp;

    int i, j;

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

    {

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

        {

            tmp.ma[i][j]=(i==j);

        }

    }

    while(k)

    {

        if(k&1) tmp=Mult(tmp,x);

        x=Mult(x,x);

        k>>=1;

    }

    return tmp;

}

int main()

{

    int t, i, j, ans, k;

    scanf("%d",&t);

    while(t--)

    {

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

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

        {

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

            {

                scanf("%d",&init.ma[i][j]);

            }

        }

        res=Pow(init,k);

        ans=0;

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

        {

            ans=(ans+res.ma[i][i])%mod;

        }

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

    }

    return 0;

}