更新記錄
【1】2020.05.21-23:49
1.完善矩陣快速冪
正文
由于普通快速冪太過于簡單，這里就先不寫了，后期再完善吧QAQ
在學習矩陣快速冪之前，我們先來了解一下矩陣這個東西
矩陣的定義：在數學中，矩陣是一個按照長方陣列排列的復數或實數集合
好了相信你已經精通了解了矩陣
接下來讓我們接觸一下它的運算
矩陣乘法
那么首先我們要明白：不是任意兩個矩陣都可以相乘 如果兩個矩陣可以相乘，那么其中一個矩陣的行數等于另一個矩陣的列數
舉幾個例子：
- 設A為2×3矩陣，B為3×2矩陣，可以相乘
- 設A為3×4矩陣，B為3×2矩陣，不可相乘
- 設A為9×4矩陣，B為1×9矩陣，可以相乘
- 設A為2×3矩陣，B為3×1矩陣，可以相乘
設A為i×k矩陣，B為k×j矩陣，那么其乘積為一個i×j矩陣
之后記公式即可
\(C_{i,j}=\sum\limits_{k=1}^{k}A_{i,k}*B_{k,j}\)
舉一個很簡單的例子：設A為2×4矩陣，B為4×2矩陣
\(A=\begin{bmatrix}0&1&2&3\\4&5&6&7\end{bmatrix}\)
\(B=\begin{bmatrix}10&11\\12&13\\14&15\\16&17\end{bmatrix}\)
\(A*B=\)
\(\begin{bmatrix}0*10+1*12+2*14+3*16&0*11+1*13+2*15+3*17\\4*10+5*12+6*14+7*16&4*11+5*13+6*15+7*17\end{bmatrix}\)
\(=\begin{bmatrix}88&94\\296&318\end{bmatrix}\)
那么接下來就很簡單了，多載一下乘號，原樣寫代碼就可以 （普通快速冪怎么寫就怎么寫）
#include<iostream>
#include<cstring>
using namespace std;
#define NUM 105
#define MOD 1000000007
#define ll long long
ll n,f;
struct matrix{
ll a[NUM][NUM];
matrix() {memset(a,0,sizeof a);}
}m,ans;
matrix operator * (matrix const &A,matrix const &B){
matrix C;int i,o,p;
for(i=1;i<=n;i++)
for(o=1;o<=n;o++)
for(p=1;p<=n;p++)
C.a[i][o]=(C.a[i][o]+A.a[i][p]*B.a[p][o]%MOD)%MOD;
return C;
}
int main(){
cin>>n>>f;
int i,o;
for(i=1;i<=n;i++){
ans.a[i][i]=1;
for(o=1;o<=n;o++)
cin>>m.a[i][o];
}
while(f){
if(f&1) ans=ans*m;
f>>=1;m=m*m;
}
for(i=1;i<=n;i++){
for(o=1;o<=n;o++)
cout<<ans.a[i][o]<<" ";
cout<<"\n";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49736.html
標籤：其他
上一篇：[Dijkstra尋路演算法]基于Unity簡單實作Dijkstra尋路演算法
下一篇：二叉樹的遍歷及常用演算法