题目描述
大家都知道斐波那契数列，现在要求输入一个整数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]
