题解 | #斐波那契数列#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def mutiply(self, matrix1, matrix2):
        res = []
        for i in range(len(matrix1)):
            temp = []
            for j in range(len(matrix2[0])):
                sum = 0
                for k in range(len(matrix2)):
                    sum += matrix1[i][k] * matrix2[k][j]
                temp.append(sum)
            res.append(temp)
        return res
            
    def matrix_quickpow(self, matrix, n:int):
        M = [[0,1], [1,1]]
        while n > 0:
            if n & 1 == 1:
                matrix = self.mutiply(M, matrix)
            n = n >> 1
            M = self.mutiply(M , M)
        return matrix
            
    def Fibonacci(self , n: int) -> int:
        # write code here
        # 矩阵快速幂
        if n < 2:
            return n
        matrix = [[1],[1]]
        result = self.matrix_quickpow(matrix, n-1)
        return result[0][0]