模板题：传送门

矩阵乘法

基本运算

结果矩阵第m行与第n列交叉位置的那个值，等于第一个矩阵第m行与第二个矩阵第n列，对应位置的每个值的乘积之和 比如：

基本性质

  1. 乘法结合律： (AB)C=A(BC)
  2. 乘法左分配律：(A+B)C=AC+BC
  3. 乘法右分配律：C(A+B)=CA+CB
  4. 矩阵乘法一般不满足交换律

矩阵快速幂

矩阵快速幂实际上就是将快速幂的数字的运算换成了矩阵，利用二分的思想快速求解

模板

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
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100+10,Mod=1000000007;
LL a[maxn][maxn];
LL ans[maxn][maxn];
LL bas[maxn][maxn];
LL tmp[maxn][maxn];
int n;
LL m;
inline void Mult(int flag){
    if(flag){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                tmp[i][j]=ans[i][j],ans[i][j]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    (ans[i][j]+=(bas[i][k]*tmp[k][j])%Mod)%=Mod;
    }
    else {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                tmp[i][j]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    (tmp[i][j]+=(bas[i][k]*bas[k][j])%Mod)%=Mod;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                bas[i][j]=tmp[i][j];
    }
}
inline void pow(LL m){
    while(m){
        if(m&1)Mult(1);
        Mult(0);
        m>>=1;
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&bas[i][j]),ans[i][j]=bas[i][j];
    pow(m-1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%d ",ans[i][j]);
        puts("");
    }
    return 0;
}