HDU （1575 Tr A）

题目分析：Tr A表示方阵A的迹（主对角线元素之和），求Tr(A^k) % 9973。

由于k最大有10^9，所以只能用矩阵二分快速幂得到A^k，最后求和即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[11][11];
};
int n,p=9973;
struct M multiply(struct M a,struct M b){
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
	return c;
}
struct M paw(struct M a,int t){
	if(t==1)
		return a;
	else{
		struct M b=paw(a,t/2);
		if(t&1){
			return multiply(multiply(b,b),a);
		}
		else
			return multiply(b,b);
	}
}
int main(){
	struct M a,b;
	int k,sum,cas;
	cin>>cas;
	while(cas--){
		scanf("%d %d",&n,&k);
		sum=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a.s[i][j]);
		/*for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				printf("%d",a.s[i][j]);*/
		b=paw(a,k);
		for(int i=1;i<=n;i++)
			sum=(sum+b.s[i][i])%p;
		printf("%d\n",sum);
	}
	return 0;

}