矩阵/快速幂 学习笔记

模板及讲解

矩阵

单位矩阵:
$$
\begin{pmatrix}
1 & 0 & 0 \\\
0 & 1 & 0 \\\
0 & 0 & 1
\end{pmatrix}
$$
空矩阵:
$$
\begin{pmatrix}
0 & 0 & 0 \\\
0 & 0 & 0 \\\
0 & 0 & 0
\end{pmatrix}
$$

矩阵加法

对应位置加起来即可,矩阵加法的数初始化为空矩阵。

矩阵乘法

定义

第一个矩阵的第$i$行的每个元素乘以第二个矩阵第$j$列的每个数的积的和就是新矩阵第$i$行$j$列的数,矩阵乘法的数初始化为单位矩阵,单位矩阵乘以任意一个矩阵是不会改变值的。

写成式子,$A$大小$a \times b$,$B$大小$b \times c$,那么$C$大小为$a \times c$,则

$$C[i,j]=\sum_{k=1}^b A[i,k]B[k,j]$$

如果$A$列数不等于$B$, 则矩阵乘法无意义

存储矩阵的时候最好用结构体,因为结构体可以直接被函数返回,而且能够较为整体化

1
2
3
4
5
6
7
8
9
10
11
12
matrix mul(matrix ai, matrix bi) {//矩阵乘法
matrix ret;
ret.init2(2, 2);
for (int i = 0; i < ai.x; i++) {
for (int j = 0; j < bi.y; j++) {
for (int k = 0; k < ai.y; k++) {
ret.ma[i][j] = (ret.ma[i][j] % MO + (ai.ma[i][k] % MO) * (bi.ma[k][j] % MO)) % MO;
}
}
}
return ret;
}

结合律

矩阵乘法具有结合律。即$(AB)C=A(BC)$

证明:
$A$大小$a \times b$,$B$大小$b \times c$,$C$大小$c \times d$,则

$$((AB)C) [i,j]$$
$$=\sum_{l=1}^d(\sum_{k=1}^b A[i, k]B[k,l])C[l,j]$$
$$=\sum_{l=1}^d\sum_{k=1}^b A[i, k]B[k,l]C[l,j]​$$
$$=\sum_{k=1}^b A[i, k] (\sum_{l=1}^dB[k,l]C[l,j])$$
$$=(A(BC)) [i,j]$$

结合律使得矩阵可以使用快速幂。

快速幂

1
2
3
4
5
6
7
8
9
int fastpow(int a,int b) { //快速幂
int ans = 1, bs = a;
while(b!=0){
if(b & 1) ans *= bs;
bs *= bs;
b >>= 1;
}
return ans;
}

矩阵快速幂

把普通的快速幂中的乘法换为矩阵乘法即可。

应用

矩阵乘法求解递推

构造矩阵使得
$$
\begin{pmatrix}
… \\\
… \\\

\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2} \\\
…\\\
F_{n-k}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1} \\\
…\\\
F_{n-k+1}
\end{pmatrix}
$$
其中可以是$F_n = F_{n-1} + F_{n-3} + F_{n-k}$,即构造矩阵的时候可以在矩阵第一行设置$0$来消掉某个$F_i$

矩阵快速幂可以优化倍增DP。

倍增DP(Bzoj 2165):ST表、LCA的pre数组求法都是这种思路,在数据大时需要矩阵快速幂的优化。

矩阵乘法求解图论问题

1、图中求$u$走$k$步(可重复走)到$v$的路径条数

图中DP:设$dp(i,x)$为走了$i$步在$x$点位置,则转移$dp(i,x)=\sum dp(i-1, y)$,其中$(x,y) \in E$
那么这个式子显然符合矩阵乘法(矩阵则为邻接矩阵),快速幂即可。
我们也可以尝试定义$dp(k,i,j)$为$i$到$j$经过$k$个点(走$k$步)的路径条数。则
$$dp(k,i,j)=\sum dp(k-1,i,k) \cdot dp(k-1,k,j)$$
压掉第一维,则$dp(i,j)=\sum dp(i,k) \cdot dp(k,j)$,发现是 Floyd 的式子
我们观察一个图的邻接矩阵,发现它自乘就模拟了上面 DP 的过程
则 Floyd 一个只有1边权的矩阵相当于是矩阵乘法。
所以一个图的邻接矩阵的$k$次方表示一点走$k$步到另一点路径条数。矩阵快速幂解决。

2、带权图中求$u$走$k$步(可重复走)到$v$的最短路长度

Bzoj 1706

图中DP:设$dp(i,x)$为走了$i$步在$x$点位置,则转移$dp(i,x)=min( dp(i-1, y)+w(y, x))$,其中$(x,y) \in E$
这里不是求方案就不能直接矩阵优化,我们尝试 Floyd 思想。
我们定义$dp(k,i,j)$为$i$到$j$经过$k$个点(走$k$步)的最短路。则
$$dp(k,i,j)=min(dp(k-1,i,k)+dp(k-1,k,j))$$
压掉第一维,则$dp(i,j)=min(dp(i,k)+dp(k,j))$
我们发现和上面式子很像,那么我们可以试图修改一下矩阵乘法定义如下

$$C[i,j]=min(A[i,k]+B[k,i])$$

易用前面方法推导结合律。则可以用矩阵快速幂加速。

其实这也体现出 Floyd 的倍增思想。相当于对一个图做几次 Floyd 就是走了几步。矩阵快速幂就是倍增的过程。
这题在图上DP思想实际上就是分层图思想,每一步对应一张新图。与 NOIP2017Day1T3 有点像

总而言之,图上DP一般有两种思路。一种是DP 想出来以后用矩阵优化。一种是Floyd 中间点思想。后者可以运用在最优化和计数问题,前者一般只能用于计数问题。视情况选择合适的算法,充分结合图论知识。


常见题型

1、构造矩阵优化递推
Q:求递推式$F_{n} = F_{n-1} + F_{n-3}$。
解:构造矩阵使用矩阵快速幂快速求解递推问题。
例题:AHSOFNU NOIP模拟题-2 T2
2、构造矩阵优化方案DP
Q:求递推式$F_{i,j} = F_{i-1,k}$。
解:构造矩阵使用矩阵快速幂快速求解方案DP问题。
例题:AHSOFNU NOIP模拟题-3 T3
3、倍增 FLoyd
4、优化倍增 DP

------ 本文结束 ------