一道經典的矩陣快速冪模板題。

傳送門1——>快速冪基本思想

傳送門2——>矩陣快速冪講解(教主傳授)

---

心路歷程

1、開始看成求主對角線元素和的n次冪了，用快速冪解得。結果壓根不對，又仔細看了下題，發現自己理解錯了。汗-_-||
2、學習快速矩陣冪的基本思想，花了大概一個小時吧，理解了快速矩陣冪后，開始嘗試解題。
3、很快就用敲出了代碼，樣例也能通過，但就是WA。于是猜想是不是取余出了問題，導致數值可能溢出？又多加了幾處取余。成功AC。
下面附上代碼。

---

AC代碼（去掉空行為40行）

#include<bits/stdc++.h> using namespace std; int n, k; struct Matrix{int a[10][10];Matrix() { memset(a, 0, sizeof(a)); } //構造函數，置0 }; Matrix mul(Matrix A, Matrix B) { //定義矩陣的運算 Matrix ret;for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; k < n; k++) { ret.a[i][j] += (A.a[i][k]*B.a[k][j])%9973;ret.a[i][j] %= 9973; //最開始WA，加上這個后AC了。應該是溢出了。} return ret; } Matrix pow(Matrix A) { //定義快速冪 Matrix ret;for(int i = 0; i< n; i++) ret.a[i][i]=1; //先定義單位矩陣(主對角線為1其余為0)while(k) {if(k%2==1) ret=mul(ret, A); //若為奇數A=mul(A, A);k /= 2;} return ret; }int main() {int T; cin>>T; while(T--) {cin>>n>>k;Matrix B;for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin >> B.a[i][j]; //輸入數組Matrix ans1=pow(B);int sum = 0;for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i==j) sum += (ans1.a[i][j]%9973); //求主對角線cout << sum%9973 << endl;} return 0; }

---

如果這篇文章對你產生了幫助，就請給博主一個小小的贊吧！大家的點贊是我創作的最大動力！

總結

以上是生活随笔為你收集整理的40行代码AC_HDU 1575 TrA 矩阵快速幂(附快速幂+矩阵快速幂的讲解)的全部內容，希望文章能夠幫你解決所遇到的問題。

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