洛谷P3390(矩阵快速幂)

发表于
字数统计: 384字 | 阅读时长 ≈ 2分钟

题目：P3390

题目描述：给定n*n的矩阵A，求A^k

输入格式：第一行，n,k第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素

输出格式：输出A^k共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7

输入样例：

1
2
3
2 1
1 1
1 1

输出样例：

1
2
1 1
1 1

快速矩阵模板题，直接套用模板即可

矩阵乘法不懂的同学点这里

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
typedef long long ll;
const int mod=1e9+7;
using namespace std;
ll n;
struct node{
	ll  a[101][101];
};
node Matrix(node x,node y)
{
	node s;
	memset(s.a,0,sizeof(s.a));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int z=0;z<n;z++)
				s.a[i][j]=(s.a[i][j]+x.a[i][z]*y.a[z][j])%mod;//矩阵乘法计算
	return s;
}
node fast_power(node x,ll k)//快速幂运算
{
	node res;
	memset(res.a,0,sizeof(res));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i==j) res.a[i][j]=1;//res为单位矩阵
	while(k)
	{
		if(k&1)	res=Matrix(res,x);
		x=Matrix(x,x);
		k>>=1;
	}
	return res;
}
int main()
{
	ll k;
	node pre;
	scanf("%lld%lld",&n,&k);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&pre.a[i][j]);
	pre=fast_power(pre,k);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n-1;j++)
			printf("%d ",pre.a[i][j]);
		printf("%d\n",pre.a[i][n-1]);
	}	
	return 0;
 }
hey!baby,站住，点它!