递推关系的题型都是基于Fibonacci序列的变种，这个题我们很容易发现它其实就是Fibonacci序列 Fibonacci序列的快速幂乘求解过程的基本思路是这样的 递推关系[a,b]=[b,a+b] 相当于[a,b]*[[0,1],[1, 1]]=[b,a+b],将 [[0,1],[1, 1]]设为base matrix 如果初始项为F(0)=[1 2]，F(n)=F(0)*base^n，此式即为Fibonacci通项的矩阵算法 对于快速幂乘，举个例子 220=410=165=16*164=16*2562 矩阵的快速幂乘就是将基数不断自乘，以减少矩阵相乘次数。由于指数是log(N)递减的，每次需要常数时间，所以其复杂度是O(logN)： 附上通过的代码： class GoUpstairs:     def countWays(self, n):         res=base=[[1,1],[1,0]]         surplus=[[1,0],[0,1]]         while(n>=2):             if n&1:                 surplus=self.mutiply(surplus,res)             res=self.mutiply(res,res)             n=n>>1         res=self.mutiply(res, surplus)         return res[0][0]00000007     def mutiply(self,a,b):         temp=[[0,0],[0,0]]         for i in range(len(a)):             for j in range(len(b)):                 for k in range(len(temp)):                     temp[i][j]+=a[i][k]*b[k][j]00000007                                return temp