矩阵/快速幂 学习笔记

发表于 | 分类于 | | + s

模板及讲解

矩阵

单位矩阵：
$$
\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$, 则矩阵乘法无意义

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

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]$$

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

快速幂

二进制

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;  
}

十进制

思路与二进制的一样，就是例如
$3^{4056}=(3^{1})^{6} \times (3^{10})^{5} \times (3^{100})^{0} \times (3^{1000})^{4}$

用来应付数据有形如$a^{100000}$的题目

矩阵快速幂

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

应用

矩阵乘法求解递推

构造矩阵使得
$$
\begin{pmatrix}
F_{n} \
F_{n-1} …
F_{n-k+1}
\end{pmatrix}

\times

\begin{pmatrix}
… \\\
… \\\
…
\end{pmatrix}
=
\begin{pmatrix}
F_{n + 1} \
F_{n} …
F_{n-k+2}
\end{pmatrix}
$$

其中第一个是初始矩阵，第二个矩阵为状态矩阵

这个乘法意思是$F_n = F_{n-1} + F_{n-3} + F_{n-k}$，即构造矩阵的时候可以在矩阵第一行设置$0$来消掉某个$F_i$

转移矩阵构造方法：若状态矩阵中的第 $x$ 个数对下个单位时间状态矩阵的第 $y$ 个数产生影响，则吧转移矩阵的第 $x$ 行第 $y$ 列赋值为适当的系数

矩阵快速幂可以优化倍增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 中间点思想。后者可以运用在最优化和计数问题，前者一般只能用于计数问题。视情况选择合适的算法，充分结合图论知识。

矩阵幂前缀和

欲求$M$的幂前缀和$M+M^2+M^3+…+M^k$，构造矩阵
$$
\begin{pmatrix}
M & I \\
0 & M \
\end{pmatrix}
$$

对这个矩阵快速幂即可。

常见题型

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

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