快速幂将 O(n) 的幂运算优化为 O(log n)。矩阵快速幂进一步将线性递推的 O(n) 求解优化为 O(k³ log n)，是竞赛和面试中的高频技巧。
一、快速幂
Mermaid · 渲染中（下方为源码）
graph LR A[幂运算] --> B[二进制分解] B --> C[O(log n) 快速幂] C --> D[矩阵版: 线性递推]
原理
利用二进制分解指数：
a^13 = a^(1101₂) = a^8 × a^4 × a^1
实现
long fastPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = result * base % mod;
}
base = base * base % mod;
exp >>= 1;
}
return result;
}应用
- 模幂运算：
a^b mod p - 模逆元：
a^(p-2) mod p（费马小定理，p 为质数） - 快速计算大数幂
二、矩阵快速幂
适用场景
线性递推：f(n) = c₁f(n-1) + c₂f(n-2) + ... + cₖf(n-k)
构造转移矩阵 A，使：