矩阵
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项
我们都知道：fn = fn − 1 + fn − 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(logn) 的复杂度求出斐波那契数列的第 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项的和
先来波证明：
设 Sn 为斐波那契数列前 n 项和
Sn = f1 + f2 + … + fn − 1 + fn
将右式变一下
$S_n=\textcolor{red}{f_2}+f_1+f_2+\dots +f_{n-1}+f_n-\textcolor{red}{f_2}$
∵fn = fn − 1 + fn − 2
∴ Sn = f3 + f2 + f3 + f4 + … + fn − 1 + fn − f2
∴ Sn = f4 + f3 + f4 + f5 + … + fn − 1 + fn − f2
以此类推：
Sn = fn + 1 + fn − f2
即 Sn = fn + 1 + fn − 1
或 Sn = fn + 2 − 1
不知各位看懂了没？
得到了最后一条式子，应该都会了吧
求斐波那契数列第x项到第y项的和
前缀和思想
求 Sy 与 Sx − 1 再一减
完事
