矩阵

Date:2023.1.13

定义

矩阵是一个 \(n\)\(m\) 列的的表格

也可以看成一个二维数组

矩阵乘法

方法

\(A\)\(m*d\) 的矩阵,\(B\)\(d*n\) 的矩阵

\(C=A*B\)

\(C\)\(m*n\) 的矩阵

\(C_{i,j}=\sum\limits_{k=1}^{d}A_{i,k}*B_{k,j}\)

即:

\(\begin{bmatrix}a1&a2\\a3&a4\end{bmatrix}*\begin{bmatrix} b1&b2\\b3&b4\end{bmatrix}=\begin{bmatrix}c1&c2\\c3&c4\end{bmatrix}\)

\(c1=a1*b1+a2*b3\)

\(c2=a1*b2+a2*b4\)

\(c3=a3*b1+a4*b3\)

\(c4=a3*b2+a4*b4\)

例:

\(\begin{bmatrix}5&5 \\6&7\end{bmatrix}*\begin{bmatrix}3&2 \\7&4\end{bmatrix}=\begin{bmatrix}50&30 \\67&40\end{bmatrix}\)

\(50=5*3+5*7\)

\(30=5*2+5*4\)

\(67=6*3+7*7\)

\(40=6*2+7*4\)

定律

结合律:\((A*B)*C=A*(B*C)\)

没有交换律,\(\color{red}A*B\neq B*A\),矩阵内的数也不能随意交换

矩阵快速幂

其实就是快速幂......

为了方便,可以重载运算符

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
#include<bits/stdc++.h>
using namespace std;
struct matrix{
int n,m;
int mx[105][105];
void in(matrix &x){
scanf("%d%d",&x.n,&x.m);
for(register int i=1;i<=x.n;i++)
for(register int j=1;j<=x.m;j++) scanf("%d",&x.mx[i][j]);
}
void print(matrix x){
for(register int i=1;i<=x.n;i++){
for(register int j=1;j<=x.m;j++) printf("%d ",x.mx[i][j]);
printf("\n");
}
}
void init(matrix &x){
for(register int i=0;i<=104;i++)
for(register int j=0;j<=104;j++) x.mx[i][j]=0;
x.n=x.m=0;
}
};
matrix operator *(matrix x,matrix y){
matrix z;
z.init(z);
z.n=x.n,z.m=y.m;
for(int i=1;i<=z.n;i++)
for(int j=1;j<=z.m;j++)
for (int k=1;k<=x.m;k++){
z.mx[i][j]+=(x.mx[i][k]*y.mx[k][j])%mod,z.mx[i][j]%=mod;
}
return z;
}
matrix fp(matrix x,long long p){
matrix z;
z.init(z);
z.n=x.n,z.m=x.m;
for(register int i=1;i<=z.n;i++) z.mx[i][i]=1;
while(p>0){
if(p&1) z=z*x;
x=x*x;
p>>=1;
}
return z;
}
matrix a,b,c;
int main(){
a.init(a),b.init(b);
a.in(a),b.in(b);
a.print(a);
b.print(b);
c=a*b;
c.print(c);
}

应用

求斐波那契数列的第\(n\)

我们都知道:\(f_n=f_{n-1}+f_{n-2}\)

但当 \(n\) 非常大时,这个会 TLE

所以我们可以运用矩阵乘法的思想,先上公式

\(\begin{bmatrix}f_n&f_{n-1}\end{bmatrix}=\begin{bmatrix}f_{n-1}&f_{n-2}\end{bmatrix}*\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

我们再来推一遍:

\(f_n=f_{n-1}+f_{n-2}\\f_{n-1}=f_{n-1}\)

接着,我们把 \(A\) 设为 \(\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

\(即A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

那不难推出:

\(\begin{bmatrix}f_n&f_{n-1}\end{bmatrix}=\begin{bmatrix}f_{n-2}&f_{n-3}\end{bmatrix}*A^2\)

继续往下一直推:

\(\begin{bmatrix}f_n&f_{n-1}\end{bmatrix}= \begin{bmatrix} f_2&f_1 \end{bmatrix} *A^{n-2}\)

这样,我们就可以用 \(O\left(\log n\right)\) 的复杂度求出斐波那契数列的第 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
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
long long nn,mod=10000000007;
struct matrix{
long long n,m;
long long mx[105][105];
void in(matrix &x){
scanf("%d%d",&x.n,&x.m);
for(register int i=1;i<=x.n;i++)
for(register int j=1;j<=x.m;j++) scanf("%d",&x.mx[i][j]);
}
void print(matrix x){
for(register int i=1;i<=x.n;i++){
for(register int j=1;j<=x.m;j++) printf("%d ",x.mx[i][j]);
printf("\n");
}
}
void init(matrix &x){
for(register int i=0;i<=104;i++)
for(register int j=0;j<=104;j++) x.mx[i][j]=0;
x.n=x.m=0;
}
};
matrix operator *(matrix x,matrix y){
matrix z;
z.init(z);
z.n=x.n,z.m=y.m;
for(int i=1;i<=z.n;i++)
for(int j=1;j<=z.m;j++)
for (int k=1;k<=x.m;k++){
z.mx[i][j]+=(x.mx[i][k]*y.mx[k][j])%mod,z.mx[i][j]%=mod;
}
return z;
}
matrix fp(matrix x,long long p){
matrix z;
z.init(z);
z.n=x.n,z.m=x.m;
for(register int i=1;i<=z.n;i++) z.mx[i][i]=1;
while(p>0){
if(p&1) z=z*x;
x=x*x;
p>>=1;
}
return z;
}
matrix a,f;
int main(){
scanf("%lld",&nn);
f.init(f),a.init(a);
f.n=1,f.m=2;
f.mx[1][1]=1,f.mx[1][2]=1;
a.m=a.n=2;
a.mx[1][1]=1,a.mx[1][2]=1;
a.mx[2][1]=1,a.mx[2][2]=0;
a=fp(a,nn-2);
f=f*a;
printf("%lld",f.mx[1][1]%mod);
}

求斐波那契数列前n项的和

先来波证明:

\(S_n\) 为斐波那契数列前 \(n\) 项和

\(S_n=f_1+f_2+\dots +f_{n-1}+f_n\)

将右式变一下

\(S_n=\textcolor{red}{f_2}+f_1+f_2+\dots +f_{n-1}+f_n-\textcolor{red}{f_2}\)

\(\because f_n=f_{n-1}+f_{n-2}\)

\(\therefore S_n=f_3+f_2+f_3+f_4+\dots +f_{n-1}+f_n-f_2\)

\(\therefore S_n=f_4+f_3+f_4+f_5+\dots +f_{n-1}+f_n-f_2\)

以此类推:

\(S_n=f_{n+1}+f_n-f_2\)

\(S_n=f_{n+1}+f_n-1\)

\(S_n=f_{n+2}-1\)

不知各位看懂了没?

得到了最后一条式子,应该都会了吧

求斐波那契数列第x项到第y项的和

前缀和思想

\(S_y\)\(S_{x-1}\) 再一减

完事