改編自：地址

第一篇介紹了如何快速求冪，這一篇介紹如何用數字快速求冪的思想，來快速求矩陣之冪

這是求矩陣A、B乘積的代碼：

const int N=100; int c[N][N]; void multi(int a[][N],int b[][N],int n) {memset(c,0,sizeof c);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j]; }

這里我直接寫的是n*n的矩陣(即方陣)，顯然兩個相乘是要一行和一列對應乘，那么矩陣乘法是需要A的行數與B的列數相等的(這是A*B的前提條件，可見矩陣的乘法是不滿足交換律的)。然而這些一般都是沒什么用的，矩陣快速冪只會用到方陣(除非題目是裸的矩陣乘法)。矩陣快速冪都是方陣也就避免的相乘的前提條件，可以放心用。

?

OK，現在可以求兩個矩陣之積，那么矩陣的“平方”和“冪”也就可以求，下面就是矩陣如何快速求冪，和第一篇的思想相同

需要用到一個小知識就是：單位矩陣與矩陣A相乘，結果仍是矩陣A

?

const int N=10; int tmp[N][N]; void multi(int a[][N],int b[][N],int n) {memset(tmp,0,sizeof tmp);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)tmp[i][j]+=a[i][k]*b[k][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=tmp[i][j]; } int res[N][N]; void Pow(int a[][N],int n) {memset(res,0,sizeof res);for(int i=1;i<=n;i++) res[i][i]=1;while(n){if(n&1)multi(res,a,n);//res=res*a;復制直接在multi里面實現了；multi(a,a,n);//a=a*an>>=1;} }

?

如上，在最后結果存在res里，如果覺得不爽也可以在pow函數的最后加一個復制，把res復制給a

?將n次矩陣相乘減少到logn次，這就是矩陣快速冪的核心妙處

通過將其他問題轉化為“求矩陣之冪”，進而運用快速冪的思想求出結果

那么，你會問，怎么會有求“矩陣之冪“這種無聊的問題呀？嘿，還真有

前兩篇是基礎，第三篇開始實例

據知后事如何，請看下回分解

轉載于:https://www.cnblogs.com/ucandoit/p/8645931.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。