依然主要還是自用

首先矩陣一條性質(zhì)的概述和證明

概述:對于一個(gè)臨接矩陣$G$來說，它自乘$G^k$次方中$G[i][j]$含義為從i走到j(luò)走k步方案數(shù).

證明:比較麻煩,我們設(shè)f[i]表示從1走到其他點(diǎn)方案數(shù),那么根據(jù)矩陣遞推優(yōu)化,k次就是轉(zhuǎn)移了k次,那么每次走一步,k次就是走了k步

最好手模一下,然后自己隨便寫一個(gè)數(shù)據(jù)驗(yàn)證一下.

然后矩陣可以優(yōu)化遞推,比如優(yōu)化菲波納契數(shù)列的遞推,暴力遞推時(shí)間復(fù)雜度是$O(n)$的用矩陣快速冪能優(yōu)化成$8*log(n)$的

具體優(yōu)化步驟,

首先把之前各項(xiàng)寫出來,

先寫出這一項(xiàng)可以由什么轉(zhuǎn)移過來,

通過添加系數(shù)的方法把各項(xiàng)算出來

就拿菲波納契數(shù)列為例

首先假設(shè)f矩陣為

$(f[n], f[n-1])$

根據(jù)橫乘豎的原則

得出$(f[n],f[n-1])$=$(f[n-1],f[n-2])\times$$\left(\begin{array}{cc}1&1\\1&0\end{array}\right)$

主要還是橫乘豎對應(yīng)好就完了

一些題目

奶牛接力跑,迷路

轉(zhuǎn)載于:https://www.cnblogs.com/znsbc-13/p/11233836.html

總結(jié)

以上是生活随笔為你收集整理的矩阵快速幂总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。