算法

$$A_n=[[1,1],[1,0]{]}^n=[[F_{n+1},F_n],[F_n,F_{n?1}]{]}^n$$

將Fn的累計計算方式轉換為矩陣乘法的計算方式。

冪計算的方式由于，存在有l(wèi)ogn算法，我在 整數(shù)冪計算方式logn 中提到了，冪計算的logn算法。

注意的是： 由于矩陣乘法比對棧的壓力比整數(shù)更大，其實一般不使用的遞歸的方式來求解。
只考慮循環(huán)的方式來做。

關于越界：

• 考慮到數(shù)可能會很大，所以就用了一個mod的操作。
• 涉及到兩個數(shù)的乘法，很可能出現(xiàn)兩個沒有越界的數(shù)的乘法直接越界，因此最好用long來避免這種情況。

class M{long x11, x12, x21, x22;static const int mod = 1000000007; public:M(long x11_=0, long x12_=0, long x21_=0, long x22_=0): x11(x11_), x12(x12_), x21(x21_), x22(x22_){}M operator*(const M& m){M ans;ans.x11 = ((this->x11 * m.x11) % mod + (this->x12 * m.x21) % mod) % mod;ans.x12 = ((this->x11 * m.x12) % mod + (this->x12 * m.x22) % mod) % mod;ans.x21 = ((this->x21 * m.x11) % mod + (this->x22 * m.x21) % mod) % mod;ans.x22 = ((this->x21 * m.x12) % mod + (this->x22 * m.x22) % mod) % mod;return ans;}long getFn(){return x12;} };class Solution {public:M fib_m(int n){M ans(1, 0, 0, 1);M tmp(1, 1, 1, 0);while (n!=0) {if (n & 1) ans = ans * tmp;tmp = tmp * tmp;n /= 2;}return ans;}int fib(int n) {M ans = fib_m(n);return ans.getFn();} };

總結

以上是生活随笔為你收集整理的【C++】log(n)斐波那契数列计算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。