矩阵

矩阵

九月 05, 2021

用矩阵来祭我的第一篇博客

感谢朱枫苓，WYX大佬为本人博客的建设做出的巨大贡献
再次特别发出大佬博客的地址，表示我对与朱枫苓大佬的敬佩
大佬自己的博客
大佬在博客园的博客

好了，来看看矩阵

  1. 加法。只有同型的矩阵才可以相加，对应的位置上面相加就可以了。
  2. 数乘。把一个矩阵拿来和一个常数相乘，每一位都乘上来就行了，没有什么多的了。
  3. 倒置。直接行列倒过来就行了。还有一个定理：A*B的倒置等于A的倒置乘以B的倒置

然后就到了重点了

乘法

矩阵乘法$A*B$ 可以做乘法的条件是A的列数要等于B的行数 然后呢乘法就是A的第几行和B的第几列对应相乘累加就是答案第几几的位置的值了。这个矩阵啊，作用非常的大，配合快速幂，可以加速状态转移，实现很多的骚操作。 下面让我们看看矩阵是如何骚操作斐波那契数列的

题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

  • $f(1) = 1$

  • $f(2) = 1$

  • $f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)$

题目描述

请你求出$ f(n) mod 1000000007$ 的值。

设一个有两个元素的$1*2$的矩阵 $A[n]=[f(n),f(n-1)]$然后这样的话$A[n-1]=[f(n-1),f(n-2)]$那么的设话 $A[n-1]*B=A[n]$ ,易得 B为
$$
\begin{bmatrix}
1&1\
1&0
\end{bmatrix}
$$

则 $f(n)$ 为 $A[1][1]*(B 的 n 次方时的第二个元素）$

代码如下：

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
//Matrix F[n]={f[n],f[n-1]}
//A={1,1
//   1,0}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll A[2][2];
const ll Mod=1000000007;
void mul(ll *a,ll b[2][2]){
    ll tmp[2];
    memset(tmp,0,sizeof(tmp));
    for(int j=0;j<=1;j++){
        for(int k=0;k<=1;k++){
            (tmp[j]+=(a[k]*b[k][j]))%=Mod;
        }
    }
    memcpy(a,tmp,sizeof(tmp));
}
void mulsel(ll (*f)[2]){
    ll tmp[2][2];
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            for(int k=0;k<=1;k++){
                (tmp[i][j]+=(f[i][k]*f[k][j]))%=Mod;
            }
        }
    }
    memcpy(f,tmp,sizeof(tmp));
}
ll pw(ll b){
    ll ans[2]={1,0};
    while(b){
        if(b&1)mul(ans,A);
        mulsel(A);
        b>>=1;
    }
    return ans[1];
} 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    A[0][0]=1;A[0][1]=1;
    A[1][0]=1;A[1][1]=0; 
    ll k;
    cin>>k;
    printf("%lld",pw(k));//快速幂 
    return 0;
}
  1. 1. 用矩阵来祭我的第一篇博客
    1. 1.1. 乘法