斐波那契数列

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n==0: return 0
        if n==1: return 1
        if n==2: return 1
        n -= 1
        a = [[1,1],[1,0]]
        m = len(a)
        
        def helper(a, b):
            c = [[0 for _ in range(m)] for _ in range(m)]
            for i in range(m):
                for j in range(m):
                    c[i][j] = sum([a[i][k]*b[k][j] for k in range(m)])
            return c
            
        def mfp(a, n):
            b = [[0 for _ in range(m)] for _ in range(m)]
            for i in range(m): b[i][i]=1  # eye matrix
            
            while n:
                # how to update a,b and n
                if n&1:
                    b = helper(b, a)
                n = n/2
                a = helper(a, a)
            
            return b
            
        c = mfp(a, n)
        return c[0][0]