学习笔记_ 矩阵乘法(ATP orz)

矩阵乘法是一种常见的递推优化

矩阵乘法基础

  • 矩阵乘法的计算: 前一个矩阵的一列上的每个数分别乘上后一个矩阵的一行的每个数, 得到的结果加起来放在结果矩阵这一行一列的交点位置
  • 矩阵乘法满足的条件: 前一个矩阵的列数 = 后一个矩阵的的行数
  • 矩阵乘法的性质:
    • 没有交换律
    • 满足结合律
    • 满足乘法分配律 $(A + B) \times C = A \times C + B \times C$
    • 转置 $(A \times B) ^ T = B ^ T \times A ^ T$
  • 乘法的代码
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= p; k++)
{
C[i][j] += a[i][k] * b[k][j];
}
}
}

矩阵乘法几点应用

优化递推

几个栗子

$1$ . 求斐波那契数列的第$n(n <= 10^9)$项mod q
递推? 通项公式?

矩乘!
观察$F[i] = F[i - 1] + F[i - 2]$发现可以只由前两项得出(废话)
于是可以构造一个矩阵$A = (F[i] F[i - 1])$代表第$i$项斐波那契数, 如何得出$F[i + 1]$和$F[i]$?
构造矩阵$B$使得$A \times B = C \cap C = (F[i + 1], F[i])$即可!
怎么构造$B$ ? …这就因题而异了…
这道题里就是
$$
B = \begin{bmatrix}
1 & 2\\
0 & 1
\end{bmatrix}
$$
, 易看出$A$每乘一遍$B$都能得出下一项, 又因为矩乘满足结合律, 于是得出$F[n] = A \times B ^ {n - 2}$
但是复杂度依然没变啊…乘方…想到了什么?
快速幂!
前面说过矩阵是可以快速幂的, 于是复杂度就优化为了$O(\log n)$?
矩乘快速幂优化fib:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define REFUN (1000000007)
using namespace std;
struct matrix
{
LL zh[2][2];
void init()
{ zh[0][0] = zh[0][1] = zh[1][0] = zh[1][1] = 0; }
matrix() {}
matrix(bool x)
{
if (x) zh[0][0] = zh[0][1] = zh[1][0] = 1, zh[1][1] = 0;
else zh[0][0] = zh[1][1] = 1, zh[1][0] = zh[0][1] = 0;
}
};
matrix cheng(matrix x, matrix y)
{
matrix re;
re.init();
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
re.zh[i][j] += (x.zh[i][k] * y.zh[k][j]) % REFUN, re.zh[i][j] %= REFUN;
return re;
}
matrix ksm(LL b)
{
if (b == 0)
return matrix(0);
if (b == 1)
return matrix(1);
matrix re = ksm(b >> 1);
re = cheng(re, re);
if (b & 1)
re = cheng(re, matrix(1));
return re;
}
int main()
{
int fib[5] = {0, 1, 1, 2, 3};
LL n;
scanf("%lld", &n);
if (n < 5)
{
printf("%d", fib[n]);
return 0;
}
printf("%lld", ksm(n).zh[1][0]);
return 0;
}

// 1 1 2 3 5 8 13 21 34

$1.5$. 上一个题如果加一个常数呐?

把矩阵的对角线扩大一位即可, 横竖都填零, 对角线上的那个点填常数即可

$2$ . 如果递推式的项不连续呐? 比如$F[n] = F[n - 1] + F[n - 2] + F[n - 4]$
$A$保留3位?

$A$矩阵的大小得是4, 虽然 $F[n]$ 用不到 $F[n - 3]$ 但是递推到 $F[n + 1]$ 就用到了啊, 只要构造好$B$矩阵, 使相乘的时候 $F[n - 3]$ 的贡献为 $0$ 即可

传送至 Luogu

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (3 + 5)
#define REFUN (1000000007)
#define LL long long
using namespace std;
struct matrix
{
int n, m;
LL zh[3][3];
void init()
{ memset(zh, 0, sizeof(zh)); }
matrix() {}
matrix(int x)
{
memset(zh, 0, sizeof(zh));
if (x > 0)
n = m = 3, zh[0][0] = zh[1][1] = zh[2][2] = 1;
else if (x == 0)
n = 1, m = 3, zh[0][0] = zh[0][1] = zh[0][2] = 1;
else
n = m = 3, zh[0][1] = zh[1][2] = zh[2][0] = zh[2][2] = 1;
}
};
matrix cheng(matrix x, matrix y)
{
matrix re;
re.init();
re.n = x.n, re.m = y.m;
for (int i = 0; i < x.n; i++)
for (int j = 0; j < y.m; j++)
for (int k = 0; k < x.m; k++)
re.zh[i][j] += x.zh[i][k] * y.zh[k][j], re.zh[i][j] %= REFUN;
return re;
}
matrix ksm(LL b)
{
if (b == 0)
return matrix(1);
if (b == 1)
return matrix(-1);
matrix re = ksm(b >> 1);
re = cheng(re, re);
if (b & 1)
re = cheng(re, matrix(-1));
return re;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
LL n;
scanf("%lld", &n);
if (n == 1)
{
puts("1");
continue;
}
printf("%d\n", cheng(matrix(0), ksm(n - 2)).zh[0][0]);
}
return 0;
}

$3$ . 求$F[n] = \sum_{i = 1 \to 10} a[i] \times F[n - i]$, $a[i]$ 输入
暴力? 前缀和?

输入的时候构造矩阵就行了啊..

1
//未完待续

在图论上的应用

又是几个栗子

$1$ . 一个无向图, 允许走回头路, 问从$A$到$B$走 $K$条路的方案数

DFS? BFS? Floyed?

把邻接矩阵(讲真这么长时间不用邻接矩阵真心想不出来这个方法) 和自己相乘1次, 得到的$G[i][j]$就是从 $i$到$j$走2条路有 $G[i][j]$种方案, 因为$G_k[i][j] = \sum G_{k - 1}[i][] \times G_{k - 1}[][j]$ , 相当于[$i$走到一个点中转到达 $j$的方案数]的总和
然后答案就是$G ^ k$咯

$1.5$ . 一个有向图, 允许走回头路, 问从$A$到$B$走 $K$ 条路的方案数

同上, 没错就是把邻接矩阵改成有向的就行(矩乘真是太棒了!)

$2$ . 一个无向图, 不允许走回头路, 问从$A$到$B$走 $K$条路的方案数

关于回头路的定义: 只要不是 [从 A 到 B, 接着从 B 到 A] 都不算回头路
DFS? BFS?

把无向边拆成两条有向边, 建一个$(2m) \times (2m)$的邻接矩阵$G$(把边看成点, 把点看成边), 只有两条边首尾相接的时候才把这两条边在矩阵上$G$相连
再做一个 $G^k$, 结了

想一想为什么: 我们要保证不走回头路, 就是要让矩阵中自己和自己不相连, 满足了这个剩下的就都跟$1$一样了…