【C++】log(n)斐波那契数列计算

偏执的太偏执、 2022-11-02 15:26 228阅读 0赞

# 算法 #

A n = \[ \[ 1 , 1 \] , \[ 1 , 0 \] \] n = \[ \[ F n + 1 , F n \] , \[ F n , F n − 1 \] \] n A\_n = \[\[1,1\],\[1,0\]\]^n = \[\[F\_\{n+1\}, F\_\{n\}\],\[F\_\{n\}, F\_\{n-1\}\]\] ^n An=\[\[1,1\],\[1,0\]\]n=\[\[Fn\+1,Fn\],\[Fn,Fn−1\]\]n

将Fn的累计计算方式转换为矩阵乘法的计算方式。

幂计算的方式由于，存在有logn算法，我在 [**整数幂计算方式logn**][logn] 中提到了，幂计算的logn算法。

**注意的是：** 由于矩阵乘法比对栈的压力比整数更大，其实一般不使用的递归的方式来求解。  
只考虑循环的方式来做。

**关于越界：**

*  考虑到数可能会很大，所以就用了一个mod的操作。
 *  涉及到两个数的乘法，很可能出现两个没有越界的数的乘法直接越界，因此最好用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();
        }
    };

[logn]: https://blog.csdn.net/a19990412/article/details/101905912?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161423482316780357275270%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=161423482316780357275270&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v2~rank_v29-1-101905912.pc_v2_rank_blog_default&utm_term=%E5%B9%82