题目：

题解：

class Solution:def fib(self, n: int) -> int:if n < 2:return nq = [[1, 1], [1, 0]]res = self.matrix_pow(q, n - 1)return res[0][0]def matrix_pow(self, a: List[List[int]], n: int) -> List[List[int]]:ret = [[1, 0], [0, 1]]while n > 0:if n & 1:ret = self.matrix_multiply(ret, a)n >>= 1a = self.matrix_multiply(a, a)return retdef matrix_multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:c = [[0, 0], [0, 0]]for i in range(2):for j in range(2):c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]return c