矩阵乘法

矩阵乘法

十二月 01, 2021

矩阵

矩阵的定义：

一个n*m的矩阵可以看作是一个二维数组

设A是$n m$矩阵，B是 $m p$矩阵

则C就是$n * p$ 矩阵 并且

矩阵乘法满足结合律，即$(AB)C$ =$A(BC)$
满足分配律，即$(A+B)C$=$AC+B*C$

矩阵的递推应用

若F1 是 $1n$ 矩阵，F2是 $nn$ 矩阵,F3=F1 F2

F1,F3可看作一维数组

这时我们发现，矩阵乘法就可以用来做一些递推式

举个image

假如一个递推式是 $f[i]=f[i-1]+f[i-2]$(斐波那契数列)

那么它的我们就可以设它的A矩阵为

A={$f[i-1]$ $f[i]$}

想要得到的C矩阵就应该是

C={$f[i]$ $f[i+1]$}

此时，我们是不是只要找到一个$nn$的B矩阵就可以使得$AB=C$

那么怎么构造B矩阵呢？首先我们要理解一下C数组

$C[i][j]$表示的应该就是A数组第i行的每个数分别乘上B数组第j行的每个数

那么对于这个题来说

我们要得到的$C[1][1]$是不是$f[i]$

那么我们只要$f[i-1]$乘上0，f[i]乘上1是不是就行了

所以说B的第一列是0,1

另外

我们观察$f[i+1]$ 显然$f[i+1]=f[i]+f[i-1]$，

所以我们要让$f[i-1]1+f[i]1$

所以B数组就是

0 1

1 1

我们可以这样写
同时我们发现，F3=F1*F2

F4=F3*F2

$F5=F4F2=F3F2F2=F1F2^3$

即$Fn=F1*F2^{n-1}$

upd:我发现了一种新的推式子的好方法：
对于

我们可以选择进行一次新的矩阵变换：

我们尝试竖着写（等会会很有用的）

那么我们这样做：
直接看看C的每一个式子是怎么推出来的，但是位置和顺序不能换，0也得写上去

把前面的每一个系数取出来
所以我们的矩阵 $B$ 最后就长成

这个是对的，不信自己试试看？

但是应该你得把A和B换一下，要不不满足矩阵乘了

最后贴一份矩阵快速幂的代码罢

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
#define int long long
using namespace std;
const int N=110;
const int mod=1e9+7;
typedef pair<int,int> P;
namespace scan{
    template <typename T>
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template <typename T>
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
int n,k;
struct Matrix{
    int a[N][N];
    Matrix(){memset(a,0,sizeof(a));}
    inline void build(){
        for(int i=1;i<=n;i++) a[i][i]=1;
    }
}A;

Matrix operator * (const Matrix &A,const Matrix &B){
    Matrix C;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
    return C;
}
Matrix ans;
inline void qpow(int k){
    while(k){
        if(k&1) ans=ans*A;
        A=A*A;
        k>>=1;
    }
}
signed main(){
    read(n),read(k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) read(A.a[i][j]);
    ans.build();
    qpow(k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            write(ans.a[i][j],' ');
        putchar('\n');   
    }
    return 0;
}