矩阵快速幂

数学与数论

说明

矩阵乘法满足结合律；二进制快速幂可加速线性递推。

分析

线性递推可以写成固定矩阵与状态向量的乘法，求第 n 项就转成矩阵的 n 次幂。矩阵乘法满足结合律，因此可使用与普通快速幂相同的二进制拆分。

图解推演

斐波那契矩阵 M=[[1,1],[1,0]] 把状态 [F(n),F(n−1)] 推到下一项。M⁵=M⁴·M，得到 [[8,5],[5,3]]。快速幂的结果必须从单位矩阵开始；矩阵乘法一般不交换，不能把任意不同转移矩阵随意换序。

查看图表代码

适用前提与边界

示例处理 2×2 矩阵；大数计算需要考虑溢出或取模。

示例输入与调用

fmt.Println(MatrixPower(Matrix{{1, 1}, {1, 0}}, 5))

运行输出

[[8 5] [5 3]]

完整 Go 示例

package main

import "fmt"

type Matrix [2][2]int

func Mul(a, b Matrix) (c Matrix) {
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			for k := 0; k < 2; k++ {
				c[i][j] += a[i][k] * b[k][j]
			}
		}
	}
	return
}
func MatrixPower(a Matrix, n int) Matrix {
	result := Matrix{{1, 0}, {0, 1}}
	for n > 0 {
		if n&1 == 1 {
			result = Mul(result, a)
		}
		a = Mul(a, a)
		n >>= 1
	}
	return result
}

func main() {
	fmt.Println(MatrixPower(Matrix{{1, 1}, {1, 0}}, 5))
}