HDOJ 1575 Tr A

Problem Description

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

Input

数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

Output

对应每组数据，输出Tr(A^k)%9973。

Sample Input

2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9

Sample Output

2
2686

矩阵快速幂的模板题

#include<iostream>

using namespace std;

const int MAX = 15;
const int MOD = 9973;

struct Matrix
{
	int mat[MAX][MAX];
};

Matrix create_identity_matrix(Matrix E, int n);		//构造单位矩阵
Matrix mat_mul(Matrix a, Matrix b, int n);			//矩阵相乘
Matrix quick_power(Matrix basic, int power, int n);	//矩阵快速幂
void input_mat(Matrix* p, int n, int m);			//输入矩阵
int mat_sum(Matrix* p, int n);						//计算主对角线和并返回取模结果

int main(void)
{
	Matrix mat_now;
	Matrix ans_now;
	int t;
	cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		input_mat(&mat_now, n, n);
		ans_now = quick_power(mat_now, k, n);
		int result = mat_sum(&ans_now, n);
		cout << result << endl;
	}
	return 0;
}

Matrix create_identity_matrix(Matrix E, int n)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i == j)
				E.mat[i][j] = 1;
			else
				E.mat[i][j] = 0;
	return E;
}

Matrix mat_mul(Matrix a, Matrix b, int n)
{
	Matrix ans;
	memset(ans.mat, 0, sizeof(ans.mat));
	//这里会看出三次循环顺序是i，k，j而不是说i，j，k，当然i， j， k也对
	//不过矩阵在计算机内存里是线性存储的所有i，k，j更快
	//也就是说i，j，k顺序计算适合人类计算而i，k，j更适合计算机计算
	for (int i = 0; i < n; i++)
		for (int k = 0; k < n; k++)
			for (int j = 0; j < n; j++)
			{
				ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
				ans.mat[i][j] %= MOD;
				//ans.mat[i][j] += a.mat[i][k] * b.mat[k][j] % MOD;
				//可能是因为优先级问题吧，这种写法在vs2019测试没问题
				//提交就会无法通过，可能是服务器用的编译器处理和vs2019不一样吧
				//这个题就因为这个卡了好久
			}
	return ans;
}


Matrix quick_power(Matrix basic, int power, int n)
{
	Matrix result;
	//下面这一行本质上没有意义
	//但是vs2019会以为你调用了未初始化变量然后报错
	//当然这个机制可以在设置关闭，如果没有关闭的话加上下面这一行不然无法通过编译
	memset(result.mat, 0, sizeof(result.mat));
	result = create_identity_matrix(result, n);	//初始化为单位矩阵
	while (power > 0)
	{
		if (power & 1)
			result = mat_mul(result, basic, n);
		basic = mat_mul(basic, basic, n);
		power >>= 1;
	}
	return result;
}

void input_mat(Matrix* p, int n, int m)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> p->mat[i][j];
}

int mat_sum(Matrix* p, int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += p->mat[i][i];
	return sum % MOD;
	//因为忘记写这个最终结果也得取余数的要求虽然算法正确
	//但是输出一直不对，卡了好久。
}