Leetcode-剑指offer-斐波那契数列-矩阵快速幂实现

迷南。 2023-07-20 12:29 95阅读 0赞

## 前情 ##

本文内容首先需要了解快速幂的实现原理，详情见 [pow(x, n)快速幂实现][pow_x_ n]

## 题目 ##

leetcode链接： [https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/][https_leetcode-cn.com_problems_fei-bo-na-qi-shu-lie-lcof]

题目描述：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
    
    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
    斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
    
    答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
    
     
    
    示例 1：
    
    输入：n = 2
    输出：1
    示例 2：
    
    输入：n = 5
    输出：5
     
    
    提示：
    
    0 <= n <= 100

## 解法 ##

朴素的解法就不写了，小学生都会TAT , 这里给出矩阵快速幂的解法

首先给出斐波那契数列定义

![\\\\ $\\cdot F(0)=0$ \\\\ $\\cdot F(1)=1$ \\\\ $\\cdot F(n)=F(n-1)+F(n-2)(n>=2)$][_cdot F_0_0_ _ _cdot F_1_1_ _ _cdot F_n_F_n-1_F_n-2_n_2]  
将![$\\cdot F(n)=F(n-1)+F(n-2)(n>=2)$][cdot F_n_F_n-1_F_n-2_n_2] 用矩阵表示则有

![$$ \\left\[\\begin\{array\}\{c\} F(n)=F(n-1)+F(n-2) \\\\ F(n-1) \\end\{array\}\\right\]=\\left\[\\begin\{array\}\{ll\} 1 & 1 \\\\ 1 & 0 \\end\{array\}\\right\] \\times\\left\[\\begin\{array\}\{c\} F(n-1) \\\\ F(n-2) \\end\{array\}\\right\] $$][_left_begin_array_c_ F_n_F_n-1_F_n-2_ _ F_n-1_ _end_array_right_left_begin_array_ll_ 1 _ 1 _ 1 _ 0 _end_array_right_ _times_left_begin_array_c_ F_n-1_ _ F_n-2_ _end_array_right_]

而![F(n-1), F(n-2)][F_n-1_ F_n-2] 有着同样的表示方法，则递推得到

![$$ \\left\[\\begin\{array\}\{c\} F(n) \\\\ F(n-1) \\end\{array\}\\right\]=\\left\[\\begin\{array\}\{ll\} 1 & 1 \\\\ 1 & 0 \\end\{array\}\\right\] \\times\\left\[\\begin\{array\}\{c\} F(n-1) \\\\ F(n-2) \\end\{array\}\\right\]=\\left\[\\begin\{array\}\{cc\} 1 & 1 \\\\ 1 & 0 \\end\{array\}\\right\]^\{2\} \\times\\left\[\\begin\{array\}\{c\} F(n-2) \\\\ F(n-3) \\end\{array\}\\right\]=\\ldots=\\left\[\\begin\{array\}\{cc\} 1 & 1 \\\\ 1 & 0 \\end\{array\}\\right\]^\{n-1\} \\times\\left\[\\begin\{array\}\{c\} F(1) \\\\ F(0) \\end\{array\}\\right\] $$][_left_begin_array_c_ F_n_ _ F_n-1_ _end_array_right_left_begin_array_ll_ 1 _ 1 _ 1 _ 0 _end_array_right_ _times_left_begin_array_c_ F_n-1_ _ F_n-2_ _end_array_right_left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_2_ _times_left_begin_array_c_ F_n-2_ _ F_n-3_ _end_array_right_ldots_left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_n-1_ _times_left_begin_array_c_ F_1_ _ F_0_ _end_array_right_]

而 ![\\left\[\\begin\{array\}\{cc\} 1 & 1 \\\\ 1 & 0 \\end\{array\}\\right\]^\{n-1\}][left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_n-1]可以用矩阵快速幂算出来，这里不再赘述矩阵乘法以及快速幂了， 则我们可以用 ![O(log(n)))][O_log_n]的时间计算出来![F(n)][F_n]，注意这里我们将2阶矩阵的乘法当作常数才可以得到这个结论。

## 代码 ##

class Solution {
    public:
        const long long mod = 1000000007;
        vector<vector<int>> mat_mul(vector<vector<int>> a, vector<vector<int>> b)
        {
            int ra = a.size(), ca = a[0].size(), rb = b.size(), cb = b[0].size();
            vector<vector<int> > res(ra, vector<int>(cb, 0)); 
            for (int k=0; k<ca; k++)
            for (int i=0; i<ra; i++)
            for (int j=0; j<cb; j++)
            {
                res[i][j] += ((a[i][k]%mod)*(b[k][j]%mod))%mod;
            }
            return res;
        }
    
        vector<vector<int>> quick_mat_pow(vector<vector<int>> a, int n)
        {
            vector<vector<int>> res = {
       {1, 0},{0, 1}};
            vector<vector<int>> p = a;
            int t = n;
            for (; t>0; t>>=1)
            {
                if (t&1) res = mat_mul(res, p);
                p = mat_mul(p, p);
            }
            return res;
        }
    
        int fib(int n) {
            vector<vector<int>> f = {
       {1}, {0}};
            if (n<2) {
               if (n==0) return 0;
               else return 1;
            }
            vector<vector<int>> base = {
       {1,1},{1,0}};
            return mat_mul(quick_mat_pow(base, n-1), f)[0][0];
        }
    };

## 最后想说; ##

我的源码都整理在了github上，剑指offer专题会分类整理（如树专题，DP专题，模拟专题，搜索专题等），github链接见下文，如果对您有帮助，请帮忙在github中star，这对我很重要！！！！ 拜托拜托~！！

### github链接： https://github.com/wjlpku/Leetcode-interview    ###

[pow_x_ n]: https://blog.csdn.net/wjlwangluo/article/details/105250346
[https_leetcode-cn.com_problems_fei-bo-na-qi-shu-lie-lcof]: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
[_cdot F_0_0_ _ _cdot F_1_1_ _ _cdot F_n_F_n-1_F_n-2_n_2]: https://private.codecogs.com/gif.latex?%5C%5C%20%24%5Ccdot%20F%280%29%3D0%24%20%5C%5C%20%24%5Ccdot%20F%281%29%3D1%24%20%5C%5C%20%24%5Ccdot%20F%28n%29%3DF%28n-1%29&plus;F%28n-2%29%28n%3E%3D2%29%24
[cdot F_n_F_n-1_F_n-2_n_2]: https://private.codecogs.com/gif.latex?%24%5Ccdot%20F%28n%29%3DF%28n-1%29&plus;F%28n-2%29%28n%3E%3D2%29%24
[_left_begin_array_c_ F_n_F_n-1_F_n-2_ _ F_n-1_ _end_array_right_left_begin_array_ll_ 1 _ 1 _ 1 _ 0 _end_array_right_ _times_left_begin_array_c_ F_n-1_ _ F_n-2_ _end_array_right_]: https://private.codecogs.com/gif.latex?%24%24%20%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%28n%29%3DF%28n-1%29&plus;F%28n-2%29%20%5C%5C%20F%28n-1%29%20%5Cend%7Barray%7D%5Cright%5D%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bll%7D%201%20%26%201%20%5C%5C%201%20%26%200%20%5Cend%7Barray%7D%5Cright%5D%20%5Ctimes%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%28n-1%29%20%5C%5C%20F%28n-2%29%20%5Cend%7Barray%7D%5Cright%5D%20%24%24
[F_n-1_ F_n-2]: https://private.codecogs.com/gif.latex?F%28n-1%29%2C%20F%28n-2%29
[_left_begin_array_c_ F_n_ _ F_n-1_ _end_array_right_left_begin_array_ll_ 1 _ 1 _ 1 _ 0 _end_array_right_ _times_left_begin_array_c_ F_n-1_ _ F_n-2_ _end_array_right_left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_2_ _times_left_begin_array_c_ F_n-2_ _ F_n-3_ _end_array_right_ldots_left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_n-1_ _times_left_begin_array_c_ F_1_ _ F_0_ _end_array_right_]: https://private.codecogs.com/gif.latex?%24%24%20%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%28n%29%20%5C%5C%20F%28n-1%29%20%5Cend%7Barray%7D%5Cright%5D%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bll%7D%201%20%26%201%20%5C%5C%201%20%26%200%20%5Cend%7Barray%7D%5Cright%5D%20%5Ctimes%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%28n-1%29%20%5C%5C%20F%28n-2%29%20%5Cend%7Barray%7D%5Cright%5D%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D%201%20%26%201%20%5C%5C%201%20%26%200%20%5Cend%7Barray%7D%5Cright%5D%5E%7B2%7D%20%5Ctimes%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%28n-2%29%20%5C%5C%20F%28n-3%29%20%5Cend%7Barray%7D%5Cright%5D%3D%5Cldots%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D%201%20%26%201%20%5C%5C%201%20%26%200%20%5Cend%7Barray%7D%5Cright%5D%5E%7Bn-1%7D%20%5Ctimes%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D%20F%281%29%20%5C%5C%20F%280%29%20%5Cend%7Barray%7D%5Cright%5D%20%24%24
[left_begin_array_cc_ 1 _ 1 _ 1 _ 0 _end_array_right_n-1]: https://private.codecogs.com/gif.latex?%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D%201%20%26%201%20%5C%5C%201%20%26%200%20%5Cend%7Barray%7D%5Cright%5D%5E%7Bn-1%7D
[O_log_n]: https://private.codecogs.com/gif.latex?O%28log%28n%29%29%29
[F_n]: https://private.codecogs.com/gif.latex?F%28n%29