题目描述：
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足如下条件的数列
数据范围：1≤n≤40
要求：空间复杂度O(1)，时间复杂度O(n) ，本题也有时间复杂度O(logn) 的解法
示例：
输入：
4
返回值：
3
说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
解题思路：
本题考察算法-动态规划算法的使用，和青蛙跳台阶一样的解法，但本文不探究那些基础解法，来研究下如何实现时间复杂度为O(logn)的解法。思路如下。
斐波那契数列为：
则有如下公式成立：
当n=2时，有：
不难得出：
则：
当知道n以后，只需要求解元矩阵的n-2次方即可，对矩阵的高幂求解，可运用快速幂算法实现提速。
快速幂算法是将高次幂拆解为多个低次幂的组合，如：
13转换为2进制是1101，即8+4+1，那我们如果求解矩阵的13次方，只需要求一次X，X的平方，X的四次方，X的八次方，然后取X的八次方乘X的四次方乘X即可，这样省下了许多运算过程。时间复杂度为O(logn)，如果用遍历的方法求解矩阵的13次方，就相当于执行了13次操作，这样的复杂度就是O(n)。
测试代码：
class Solution { public: int Fibonacci(int n) { // 1和2时为1 if(n == 1 || n == 2) return 1; // 根据斐波那契数列可知，元矩阵如下 vector<vector<int>> element={{1,1},{1,0}}; // 元矩阵高幂运算，用快速幂算法求解 vector<vector<int>> result=Counting(element, n-2); return result[0][0]+result[0][1]; } // 快速幂算法 vector<vector<int>> Counting(vector<vector<int>> element,int n){ // 初始化为单元矩阵 vector<vector<int>> result={{1,0},{0,1}}; // 基数矩阵 vector<vector<int>> base=element; // 右移幂数，可快速完成求解 for(;n!=0;n>>=1) { // 当前位数为1时，矩阵相乘 if((n&1)!=0) { result=MatrixCalculation(result, base); } // 基数矩阵升级幂数 base=MatrixCalculation(base, base); } return result; } // 矩阵求解 vector<vector<int>> MatrixCalculation(vector<vector<int>> a,vector<vector<int>> b){ vector<vector<int>> result(a.size(),vector<int>(b[0].size(),0)); for(int i=0;i<a.size();++i) { for(int j=0;j<b[0].size();++j) { for(int k=0;k<a[0].size();++k) { result[i][j]+=a[i][k]*b[k][j]; } } } return result; } };
