题目链接:洛谷

题解部分

很奇怪。翻阅了全部的题解,貌似没有一篇的快速幂是用递归的方式写的(可能是我眼瞎)。 那么我的代码就是用递归的方式所写的题解。

矩阵快速幂用到的方法就是矩阵乘法+快速幂。掌握了这两道题目,就可以轻轻松松的AC这道题目了。

快速幂

如果不会快速幂的可以去P1226
【模板】快速幂||取余运算
这道题目。

对于矩阵乘法来说,就是一个公式。对于矩阵$a[i][m]*a[m][j]$来说,执行矩阵乘法有以下公式:

$c[i][j]=\sum\limits_{k=1}^ma_{i,k}*b_{k,j}$

代码:

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
//这个代码并未重载运算符,而是复制过去的
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007ll
using namespace std;
int n;ll k;
ll num;
ll a[110][110],b[110][110],c[110][110];
void copy() {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=c[i][j];
memset(c,0,sizeof(c));
}
void z1() {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) //第i行第j列
for(int k=1;k<=n;k++)
c[i][j]=(c[i][j]+b[i][k]*b[k][j])%mod;
copy();
}
void z2() {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]=(c[i][j]+b[i][k]*a[k][j])%mod;
copy();
}
void get_pow(ll p) {
if(p==1) return;
get_pow(p>>1);
z1();
if(p&1) z2();
}
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j],b[i][j]=a[i][j];
get_pow(k);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++)
printf("%lld ",b[i][j]);
printf("\n");
}
return 0;
}