矩阵乘法与快速幂

<div class="blogpost-body cnblogs-markdown" id="cnblogs_post_body">
<div class="toc">
 目录
 <div class="toc-list">
<ul><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E4%B8%8E%E5%BF%AB%E9%80%9F%E5%B9%82">矩阵乘法与快速幂</a>
 <ul><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95">矩阵乘法</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E7%9A%84%E7%BB%93%E5%90%88%E5%BE%8B">矩阵乘法的结合律</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#floyd-%E7%AE%97%E6%B3%95">Floyd 算法</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E5%BF%AB%E9%80%9F%E5%B9%82">快速幂</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E7%BB%93%E5%90%88%E5%BE%8B%E7%9A%84%E5%BA%94%E7%94%A8">矩阵乘法结合律的应用</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#%E4%BD%BF%E7%94%A8%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E5%BF%AB%E9%80%9F%E5%B9%82%E6%B1%82%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97">使用矩阵乘法（快速幂）求斐波那契数列</a></li><li><a href="https://blog.csdn.net/baigao66238598/article/details/102266390#p2886-usaco07nov%E7%89%9B%E7%BB%A7%E7%94%B5%E5%99%A8cow-relays">P2886 [USACO07NOV]牛继电器Cow Relays</a></li></ul></li></ul>
 </div>
</div>
<h1 id="矩阵乘法与快速幂">矩阵乘法与快速幂</h1>
<hr>
<hr>
<h2 id="矩阵乘法">矩阵乘法</h2>
定义矩阵\(A\)，\(B\)，其中\(A\)的大小为\(a \times b\)，\(B\)的大小为\(b \times c\)，对于矩阵\(C=AB\)中的每一个元素\(C(i.j),~i\in [1, a],~j\in [1,c]\)，存在以下： \[ C(i,j) = \sum_{k=1}^bA(i,k) \times B(k,j) \]
<h2 id="矩阵乘法的结合律">矩阵乘法的结合律</h2>
矩阵乘法存在结合律，首先定义矩阵\(A_{a\times b},~B_{b\times c},~C_{c\times d}\)，存在\((AB)C = A(BC)\)。证明：
对于\(i\in [1, a],~j\in [1,d]\)，有： \[ \begin {align} ((AB)C)(i,j) &= \sum_{l=1}^c(\sum_{k=1}^b A(i,k)\times B(k,l))\times C(l,j) \\ &= \sum_{k=1}^b \sum_{l=1}^c A(i,k)\times B(k,l) \times C(l,k) \\ &= \sum_{k=1}^b A(i,k)\times (\sum_{l=1}^c B(k,l)\times C(l,k)) \\ &= (A(BC))(i,j) \end {align} \] 由此，可以证明，矩阵的乘法具有结合律。
<h2 id="floyd-算法">Floyd 算法</h2>
Floyd算法的主要目的是在一张图上求任意两点之间的最短路，而最短路的核心思想其实可以由一个方程来表达： \[ dis[i][j] = \min_{j \in [1,n]}\{dis[i][j],~ dis[i][k] + dis[k][j]\} \] 其表示\(i \rightarrow j\)的最短路。
但是它的初始化值得注意，其应该初始化为一个图论的单位矩阵，即主对角线的值为\(0\)，其余值均为\(\infty\)的一个“单位矩阵”，可以如下定义： \[ dis[i][j] = \begin {cases} \infty ~~~~~~~&i≠j \\ ~0 &i=j \end {cases} \] 为了实现上述思想，以下为代码实现：
<pre class="blockcode"><code class="language-cpp"><code>for (int k = 1; k <= n; k ++)
 for (int i = 1; i <= n; i ++)
 for (int j = 1; j <= n; j ++)
 if (m[i][k] + m[k][j] < m[i][j])
 m[i][j] = m[i][k] + m[k][j];</code></code></pre>
注：Floyd算法的k的那层循环必须在最外面，否则有些值无法被更新。
<h2 id="快速幂">快速幂</h2>
如果我们要计算\(a^n\)，则会将\(a\)乘\(n\)次，时间复杂度为\(O(n)\)，而这太浪费时间了，为此，有了快速幂之中算法，快速幂可以将时间复杂度降为\(O(\log n)\)，其本质就是将指数化为一个\(2\)进制数来进行记忆化的乘法，现在假设有一个需求要求\(a^{13}\)，我们可以试着将\(13\)化为二进制：\(13=(1101)_2\)，也就是说： \[ a^{13} &#