LCR 126. 斐波那契数 #
链接 #
题目 #
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 100
解答 #
矩阵快速幂
class Solution:
def fib(self, n: int) -> int:
MOD = int(1e9 + 7)
# Base cases
if n == 0:
return 0
if n == 1:
return 1
# A matrix to represent the transformation [1 1; 1 0]
transformation_matrix = [[1, 1], [1, 0]]
# Fast exponentiation to compute the transformation matrix raised to the power of n
def matrix_multiply(A, B, mod):
result = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
for k in range(2):
result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % mod
return result
def matrix_pow(matrix, exponent, mod):
result = [[1, 0], [0, 1]] # Identity matrix
while exponent > 0:
if exponent % 2 == 1:
result = matrix_multiply(result, matrix, mod)
exponent //= 2
matrix = matrix_multiply(matrix, matrix, mod)
return result
# Calculate the nth Fibonacci number using matrix exponentiation
transformation_matrix_pow = matrix_pow(transformation_matrix, n - 1, MOD)
result = transformation_matrix_pow[0][0] * 1 + transformation_matrix_pow[0][1] * 0
return result % MOD
首先，我们来了解一下斐波那契数列和矩阵的关系。对于斐波那契数列，我们有如下的递推关系：
F(n) = F(n-1) + F(n-2)
其中，F(0) = 0, F(1) = 1。
我们可以将这个递推关系表示为一个矩阵的形式：
| F(n) | | a b | | F(n-1) |
| | = | | * | |
| F(n-1)| | c d | | F(n-2) |
观察数列的前几项：0, 1, 1, 2，代入：
| 2 | | a b | | 1|
| | = | | * | |
| 1 | | c d | | 1|
| 1 | | a b | | 0|
| | = | | * | |
| 1 | | c d | | 1|
我们可以得到：
2 = a + b
1 = c + d
1 = b
1 = d
从而：
a = 1, b = 1, c = 0, d = 1
因此递推关系为：
| F(n) | | 1 1 | | F(n-1) |
| | = | | * | |
| F(n-1)| | 1 0 | | F(n-2) |
其中，左边的矩阵表示的是当前的状态，右边的矩阵表示的是一步转移的关系。这样，我们就可以通过矩阵的快速幂来计算斐波那契数列的第 n 个数。
左乘一次可以得到一次转移的结果，左乘两次可以得到两次转移的结果，以此类推。对于 n 次：
| F(n) | | 1 1 | ^ (n-1) | F(1) |
| | = | | | |
| F(n-1)| | 1 0 | | F(0) |
而其中的矩阵的 n-1 次幂可以通过矩阵的快速幂来计算。
接下来，我们来看代码的实现：
- 首先，定义了一个矩阵 transformation_matrix，表示的是一步转移的关系。
- 定义了一个函数 matrix_multiply，用于计算两个矩阵的乘积。
- 定义了一个函数 matrix_pow，用于计算矩阵的快速幂。这个函数使用了分治的思想，将指数不断地二分，直到指数为 0。如果当前指数是奇数，那么就将结果矩阵乘以当前的矩阵；否则，只更新矩阵的值。
- 最后，我们调用 matrix_pow 函数来计算 transformation_matrix 的 n-1 次幂，然后通过乘以初始状态 [1, 0] 来得到斐波那契数列的第 n 个数。 整个算法的时间复杂度是 O(logn)，这是因为矩阵快速幂的时间复杂度是 O(logn)，而矩阵乘法的时间复杂度是 O(1)。