参考斐波那契数列 - 基于矩阵乘法的log(n)算法

# f = [0, 1, 1, 2, 3, 5, 8, 13]
# dt = {i:v for i, v in enumerate(f)}

# def fib_0(n):
#     if n in dt: return dt[n]
#     dt[n] = fib_0(n - 2) + fib_0(n - 1)
#     return dt[n]


# class Solution(object):
#     def Fibonacci(self, n):
#         """
#         :type n: int
#         :rtype: int
#         """
#         return fib_0(n)


class Mat(object):
    def __init__(self, a11, a12, a21, a22):
        self.a11, self.a12, self.a21, self.a22 = a11, a12, a21, a22
    def mul(self, m2):
        m1 = self
        return Mat( m1.a11 * m2.a11 + m1.a12 * m2.a21,    m1.a11 * m2.a12 + m1.a12 * m2.a22,
                    m1.a21 * m2.a11 + m1.a22 * m2.a21,    m1.a21 * m2.a12 + m1.a22 *m2.a22)
    def __repr__(self):
        return str([self.a11, self.a12]) + '\n' + str([self.a21, self.a22])

E = Mat(1, 0,
        0, 1)
Fib_1 = Mat(0, 1,
            1, 1)

def mpower(mat, n):
    assert(n >= 0)
    res = E
    x = mat
    while n:
        if n & 1:
            res = res.mul(x)
        x = x.mul(x)
        n >>= 1
    return res

# print(mpower(Mat(0, 1, 1, 1), 4))

class Solution(object):
    def Fibonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2: return max(0, n)
        return mpower(Fib_1, n - 1).a22