题解 | #斐波那契数列#

# -*- coding:utf-8 -*-
class Solution:
    @staticmethod
    def multiMatrix(a,b):
        c =[[0 for i in range(len(b[0]))] for i in range(len(a))]
        for i in range(len(a)):
            for j in range(len(b[0])):
                for k in range(len(a[0])):
                    c[i][j] += a[i][k]*b[k][j]
        return c

    def matrixPower(self,temp,p):
        k = 0
        while p > 0:
            if  p%2 == 1:
                if k == 0:
                    result = temp
                    k = 1
                else:
                    result = self.multiMatrix(result,temp)
            temp = self.multiMatrix(temp,temp)
            p //= 2
        return(result[0][0]+result[0][1])
    def Fibonacci(self, n):
        # write code here
        if (n == 1) | (n == 2):
            return 1
        temp = [[1,1],[1,0]]
        return self.matrixPower(temp,(n-2))