題意：
? ? ? 求斐波那契后四位，n <= 1,000,000,000.
思路：
? ? ? ?簡單矩陣快速冪，好久沒刷矩陣題了，先找個最簡單的練練手，總結下矩陣推理過程，其實比較簡單，關鍵是能把問題轉換成矩陣的題目，也就是轉換成簡單加減地推式，下面說下怎么樣根據遞推式構造矩陣把，這個不難，我的習慣是在中間插矩陣，就是比如斐波那契
a[n] = a[n-1] + a[n-2];


我的習慣是這樣，首先要知道這個式子是有連續的兩個項就可以推出第三個項
那么?
? ? ?
a1 a2 ? 0 ?1 ?a2 ?a3 ? 這樣就直接出來了中間矩陣，然后快速冪處理，這個是 ? ? ? ? ?
? ? ? ? 1 ?1 ? ? ? ? ? 最簡單的了，一般都是要想辦法各種轉換，然后在構造式子
? ? ? ? ? ? ? ? ? ? ? ?然后在快速冪，還有注意，矩陣可以把最下面那個循環拿到上面

? ? ? ? ? ? ? ? ? ? ? ?然后通過if(mat[i][k])來優化，我下面的用了，這個要看0出現 ? ? ? ? ? ? ? ? ? ? ? 的多不多（比較重要），還有可以通過調換循環位置（這個是底 ? ? ? ? ? ? ? ? ? ? ? 層優化，不在算法范圍之內）優化，推薦一個好題，杭電上有個 ? ? ? ? ? ? ? ? ? ? ? 叫 什么什么233的那個，記得當時做那個題做的比較爽。

#include<stdio.h> #include<string.h>#define MOD 10000typedef struct {int mat[3][3]; }M;M matM(M a ,M b) {M c;memset(c.mat ,0 ,sizeof(c.mat));for(int k = 1 ;k <= 2 ;k ++)for(int i = 1 ;i <= 2 ;i ++)if(a.mat[i][k])for(int j = 1 ;j <= 2 ;j ++)c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;return c; }M qPowMat(M a ,int b) {M c;memset(c.mat ,0 ,sizeof(c.mat));for(int i = 1 ;i <= 2 ;i ++)c.mat[i][i] = 1;while(b){if(b&1) c = matM(c ,a);a = matM(a ,a);b >>= 1;}return c; }int main () {int n ,i;M star ,ans;star.mat[1][1] = 0;star.mat[1][2] = star.mat[2][1] = star.mat[2][2] = 1;while(~scanf("%d" ,&n) && n != -1){if(n == 0){printf("0\n");continue;}if(n == 1){printf("1\n");continue;}ans = qPowMat(star ,n);printf("%d\n" ,(0 * ans.mat[1][1] + 1 * ans.mat[2][1]) % MOD);}return 0; }

總結

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

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