学步园

    这道题要求求解给定方阵的幂，我重载了一个幂运算符，发现C++的运算符很强大很好用！

    这道题的URL：http://acm.hdu.edu.cn/showproblem.php?pid=1575；

    我的AC代码。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

struct Matrix
{
	int d[10][10];
	static int size;

	Matrix()
	{
		memset(d, 0, sizeof(d));
	}

	void makeUnit()
	{
		for(int i=0; i<size; i++) d[i][i] = 1;
	}

	friend Matrix operator *(Matrix a, Matrix b)
	{
		Matrix m; //结果矩阵

		for(int r=0; r<a.size; r++)
			for(int c=0; c<a.size; c++)
			{
				for(int i=0; i<a.size; i++) 
					m.d[r][c] = m.d[r][c] + a.d[r][i] * b.d[i][c];
				m.d[r][c] %= 9973;
			}
		return m;
	} 

	//高效求解矩阵的幂
	friend Matrix operator ^(Matrix m, int n)
	{
		Matrix r;
		Matrix f = m;
		r.makeUnit();

		for(; n; n>>=1)
		{
			if(n & 1)	r = r * f;
			f = f * f;
		}
		return r;
	}
};

int Matrix::size = 0;

int main()
{
	int n, cases, pow, cnt;
	Matrix a, r;
	scanf("%d", &cases);
	while(cases--)
	{
		cnt = 0;
		scanf("%d%d", &n, &pow);
		Matrix::size = n;

		for(int r=0; r<n; r++)
			for(int c=0; c<n; c++)	scanf("%d", *(a.d + r) + c);

		r = a^pow;

		for(int i=0; i<n; i++) cnt = (cnt + r.d[i][i]) % 9973;
		printf("%d\n", cnt);
	}
	system("pause");
	return 0;
}