【HDU】1575 - Tr A（矩阵快速幂）

FishWang

发布于 2025-08-27 09:26:24

14900

代码可运行

运行总次数：0

代码可运行

点击打开题目

Tr A

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4330 Accepted Submission(s): 3241

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

Sample Output

   2
2686

Author

xhd

Source

HDU 2007-1 Programming Contest

矩阵快速幂的裸题了，写矩阵的时候还是要仔细！

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MOD 9973
#define CLR(a,b) memset(a,b,sizeof(a))
struct Matrix
{
	__int64 a[14][14];
	int w,h;
}pr,ans;
void init(int n)		//n阶矩阵 
{
	pr.h = pr.w = n;
	ans.w = ans.h = n;
	CLR(ans.a,0);
	for (int i = 1 ; i <= n ; i++)		//单位矩阵 
		ans.a[i][i] = 1;
}
Matrix Matrix_multiply(Matrix x,Matrix y)
{
	Matrix t;
	t.h = x.h;
	t.w = y.w;
	CLR(t.a,0);
	for (int i = 1 ; i <= x.h ; i++)
	{
		for (int j = 1 ; j <= x.w ; j++)
		{
			if (x.a[i][j] == 0)
				continue;
			for (int k = 1 ; k <= y.w ; k++)
				t.a[i][k] = (t.a[i][k] + x.a[i][j] * y.a[j][k] % MOD) % MOD;
		}
	}
	return t;
}
void Matrix_mod(int n)
{
	while (n)
	{
		if (n & 1)
			ans = Matrix_multiply(pr , ans);
		pr = Matrix_multiply(pr,pr);
		n >>= 1;
	}
}
int main()
{
	int u;
	scanf ("%d",&u);
	int n,k;
	while (u--)
	{
		scanf ("%d %d",&n,&k);
		init(n);
		for (int i = 1 ; i <= n ; i++)
			for (int j = 1 ; j <= n ; j++)
				scanf ("%I64d",&pr.a[i][j]);
		Matrix_mod(k);		//快速幂
		__int64 res = 0;
		for (int i = 1 ; i <= n ; i++)
			res = (res + ans.a[i][i]) % MOD;
		printf ("%I64d\n",res);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数据