什么是矩阵快速幂？

矩阵快速幂是一种高效计算矩阵幂次的算法，基于快速幂思想，将时间复杂度从 O(n) 优化到 O(log n)。

基本思想

对于矩阵 A 的 n 次幂，我们可以利用二进制分解：

A^n = - 如果 n = 0：单位矩阵 I- 如果 n = 1：A- 如果 n 是偶数：A^(n/2) × A^(n/2)- 如果 n 是奇数：A^((n-1)/2) × A^((n-1)/2) × A

矩阵快速幂实现

def matrix_mult(A, B): """此函数用于执行矩阵乘法操作""" n = len(A) m = len(B[0]) p = len(B) # 初始化结果矩阵，元素全为 0 result = [[0] * m for _ in range(n)] for i in range(n): for j in range(m): for k in range(p): result[i][j] += A[i][k] * B[k][j] return resultdef matrix_power(matrix, power): """此函数用于实现矩阵的快速幂运算""" n = len(matrix) # 初始化结果矩阵为单位矩阵 result = [[1 if i == j else 0 for j in range(n)] for i in range(n)] base = matrix while power > 0: if power & 1: # 若当前二进制位为 1 result = matrix_mult(result, base) base = matrix_mult(base, base) # 矩阵进行平方运算 power >>= 1 # 二进制位右移一位 return resultLeetCode 应用场景

1. 斐波那契数列 (LeetCode 509)

问题：计算第 n 个斐波那契数。

矩阵表示：

[ F(n) ] = [ 1 1 ]^(n-1) [ F(1) ][ F(n-1) ] [ 1 0 ] [ F(0) ]

解决方案：

def fib(n: int) -> int: if n == 0: return 0 if n == 1: return 1 # 基础矩阵 base = [[1, 1], [1, 0]] # 计算 base^(n-1) result_matrix = matrix_power(base, n - 1) # [F(n), F(n-1)] = result_matrix × [F(1), F(0)] return result_matrix[0][0]

2. 爬楼梯问题 (LeetCode 70)

问题：每次可以爬 1 或 2 个台阶，有多少种方法爬到第 n 阶。

矩阵表示：

[ f(n) ] = [ 1 1 ]^(n-1) [ f(1) ] [ f(n-1) ] [ 1 0 ] [ f(0) ]

解决方案：

def climbStairs(n: int) -> int: if n == 1: return 1 if n == 2: return 2 base = [[1, 1], [1, 0]] result_matrix = matrix_power(base, n - 1) # f(n) = result_matrix[0][0] * f(1) + result_matrix[0][1] * f(0) return result_matrix[0][0] * 1 + result_matrix[0][1] * 1

3. 统计元音字母序列的数目 (LeetCode 1220)

问题：计算满足特定规则的元音字母序列数量。

解决方案：

def countVowelPermutation(n: int) -> int: MOD = 10**9 + 7 # 状态转移矩阵 # a->e, e->a/i, i->a/e/o/u, o->i/u, u->a transition = [ [0, 1, 0, 0, 0], # a [1, 0, 1, 0, 0], # e [1, 1, 0, 1, 1], # i [0, 0, 1, 0, 1], # o [1, 0, 0, 0, 0] # u ] # 计算转移矩阵的 (n-1) 次幂 result_matrix = matrix_power_mod(transition, n - 1, MOD) # 初始状态：每个元音字母都可以作为开头 initial = [1, 1, 1, 1, 1] # 计算结果 total = 0 for i in range(5): for j in range(5): total = (total + result_matrix[i][j] * initial[j]) % MOD return totaldef matrix_mult_mod(A, B, mod): """带模数的矩阵乘法""" n = len(A) m = len(B[0]) p = len(B) result = [[0] * m for _ in range(n)] for i in range(n): for j in range(m): for k in range(p): result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % mod return resultdef matrix_power_mod(matrix, power, mod): """带模数的矩阵快速幂""" n = len(matrix) result = [[1 if i == j else 0 for j in range(n)] for i in range(n)] base = matrix while power > 0: if power & 1: result = matrix_mult_mod(result, base, mod) base = matrix_mult_mod(base, base, mod) power >>= 1 return result

适用问题特征

矩阵快速幂适用于以下类型的问题：

线性递推关系：如斐波那契数列、爬楼梯等状态转移问题：如有限状态自动机、图上的路径计数动态规划优化：当状态转移可以表示为矩阵形式时

时间复杂度对比

方法

时间复杂度

空间复杂度

直接计算

O(n)

O(1)

矩阵快速幂

O(log n)

O(1)

总结

矩阵快速幂是解决线性递推问题的高效工具，特别适用于：

需要计算大数情况（n 很大）递推关系可以表示为矩阵形式需要优化时间复杂度从 O(n) 到 O(log n)

在 LeetCode 中，遇到类似斐波那契数列、状态转移计数等问题时，考虑使用矩阵快速幂进行优化。