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

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

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

---

傳送門3.1——>HDU-1575（經典矩陣快速冪模板題1）

傳送門3.2——>HDU-1575題解

傳送門4.1——>HDU-1757（經典矩陣快速冪模板題2）

傳送門4.2——>HDU-1757題解

---

心路歷程

由于昨天刷了兩道題，今天想著直接秒掉然后開下個專題。首先通過基本的代碼求出規律，得到f(1)=2, f(2)=4, f(3)=6, f(4)=9, f(5)=15。(如果覺得不把握可以多算幾個，待會給出測試代碼)。得出公式： f[n]=f[n-1]+f[n-3]+f[n-4] 。 很快把代碼敲出來了。 但總是無法通過。

d了兩個小時的BUG，心態爆炸。最后發現：f(n)等于對應一列的矩陣值相加，而不是第一項，第三項和第四項相加(知識還是不扎實啊！)。 改動后，成功AC。

涉及的原理在傳送門里。寫的很詳細。不貼解題過程了。萬變不離其宗嘛

代碼一共分為五個部分實現，都在注釋里詳細的標注了。分塊理解會更簡單一些。

---

測試代碼：

舉例：找出5位隊列符合條件的個數， 列5個for循環， 求出不符合條件的個數x，用2^5減x，得到的就是符合條件的個數。 其余位數同理。

#include<iostream> #include<string> using namespace std; char a[2] = {'f', 'm'}; int main() {string s[70]; int i = 0;for(int q=0;q<2;q++) {for(int w=0;w<2;w++) {for(int e=0; e<2; e++) {for(int r=0;r<2;r++) {for(int t=0;t<2;t++) {for(int y=0;y<2;y++) {s[i] += a[y];s[i] += a[t];s[i] += a[r];s[i] += a[e];s[i] += a[w];s[i] += a[q];i++;}}}}}}int sum = 0;for(int j = 0; j < i; j++) {int find1 = s[j].find("fmf");int find2 = s[j].find("fff");if(find1!=-1 || find2!=-1) sum++;}cout << sum; return 0; }

---

AC代碼：

#include<iostream> #include<cstring> using namespace std; int L, M; struct Matrix{ //1、結構體 int a[4][4];Matrix() { memset(a, 0, sizeof(a)); } //構造函數 }; Matrix mul(Matrix A, Matrix B) {Matrix ret;for(int i=0; i<4; i++) for(int j=0; j<4; j++) {for(int k=0; k<4; k++) ret.a[i][j] += (A.a[i][k] * B.a[k][j])%M;ret.a[i][j] %= M;}return ret; }Matrix pow(Matrix A, int n) {Matrix ret;for(int i=0; i<4; i++) ret.a[i][i]=1; //單位矩陣 while(n) {if(n%2==1) ret=mul(ret, A);A = mul(A, A);n /= 2;}return ret; } int main() {while(cin>>L>>M) {//2、特判 if(L == 1) { cout << 2%M << endl; continue; } if(L == 2) { cout << 4%M << endl; continue; }if(L == 3) { cout << 6%M << endl; continue; }if(L == 4) { cout << 9%M << endl; continue; } //3、構造矩陣Matrix B;B.a[0][0] = B.a[0][2] = B.a[0][3]=1;B.a[1][0] = B.a[2][1] = B.a[3][2]=1;//4、快速冪Matrix ans1 = pow(B, L-4); //為什么f(n)的公式中明明沒有第二項，這里為什么加上了？//因為在矩陣冪乘過程中，第二項可能不為0，而f(n)=這一行的相加和。因此少一項，就錯了。 int sum = ((ans1.a[0][0]*9)%M+(ans1.a[0][1]*6)%M+(ans1.a[0][2]*4)%M+(ans1.a[0][3]*2)%M)%M;cout << sum << endl;} return 0; }

---

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

總結

以上是生活随笔為你收集整理的43行代码AC_HDU-2604 Queuing（矩阵快速幂，附详细的知识讲解、模板例题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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