矩阵
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}\) 再一减
完事
