HDU1575Tr A（矩阵快速幂）

解题思路：我的第一题矩阵快速幂，一定要敲熟模板！！！

AC代码如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<string>
#include<map>
using namespace std;
#define MAX 11

typedef struct
{
	int a[MAX][MAX];
}Det;

int ksm(int a,int b,int c)
{
	int ans=1;
	a%=c;
	while(b)
	{
		if(b&1) ans=(ans*a)%c;
		b>>=1;
		a=(a*a)%c;
	}
	return ans;
}

Det mul(Det a,Det b,int n,int MOD)
{
	Det c;
	int i,j,k;
	memset(c.a,0,sizeof(c.a));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
			{
				c.a[i][j]+=a.a[i][k]*b.a[k][j];
				c.a[i][j]%=MOD;
			}
	return c;
}

Det mulksm(Det a,int n,int m,int MOD)
{
	Det b;
	int i,j,k;
	memset(b.a,0,sizeof(b.a));
	for(i=1;i<=n;i++)
		b.a[i][i]=1;
	while(m)
	{
		if(m&1) b=mul(b,a,n,MOD);
		m>>=1;
		a=mul(a,a,n,MOD);
	}
	return b;
}

int main()
{
	int n,i,j,k,t,sum;
	Det a;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		sum=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				cin>>a.a[i][j];
		a=mulksm(a,n,k,9973);
		for(i=1;i<=n;i++)
			sum+=a.a[i][i];
		cout<<sum%9973<<endl;
	}
	return 0;
}