C语言矩阵快速幂详解（从零开始掌握快速幂优化技巧）

为什么需要矩阵快速幂？

在解决递推问题（如斐波那契数列）时，若直接使用递归或循环，当 n 很大（例如 10^9）时会超时。而利用C语言实现矩阵快速幂，可以将时间复杂度降至 O(log n)，轻松应对大数据。

前置知识：矩阵乘法

在实现矩阵快速幂前，你需要了解两个矩阵如何相乘。假设有两个 2×2 矩阵 A 和 B：

// 矩阵乘法示例（2x2）void multiply(int a[2][2], int b[2][2], int res[2][2]) {    for (int i = 0; i < 2; i++) {        for (int j = 0; j < 2; j++) {            res[i][j] = 0;            for (int k = 0; k < 2; k++) {                res[i][j] += a[i][k] * b[k][j];            }        }    }}

矩阵快速幂的核心思想

和整数快速幂类似，我们利用以下性质：

• 若 n 为偶数：A^n = (A^(n/2))²
• 若 n 为奇数：A^n = A × A^(n-1)

通过不断将指数除以 2，我们最多只需 log₂(n) 次矩阵乘法。

完整 C 语言实现

下面是一个通用的 2×2 矩阵快速幂实现，可用于求解斐波那契数列第 n 项：

#include <stdio.h>#include <string.h>// 定义矩阵大小#define N 2// 矩阵乘法void matMul(long long a[N][N], long long b[N][N], long long res[N][N]) {    long long tmp[N][N];    memset(tmp, 0, sizeof(tmp));        for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            for (int k = 0; k < N; k++) {                tmp[i][j] += a[i][k] * b[k][j];            }        }    }        // 复制结果    memcpy(res, tmp, sizeof(tmp));}// 矩阵快速幂void matPow(long long base[N][N], long long exp, long long res[N][N]) {    // 初始化 res 为单位矩阵    memset(res, 0, sizeof(long long) * N * N);    for (int i = 0; i < N; i++) {        res[i][i] = 1;    }        long long temp[N][N];    memcpy(temp, base, sizeof(temp));        while (exp > 0) {        if (exp & 1) {            matMul(res, temp, res);        }        matMul(temp, temp, temp);        exp >>= 1;    }}// 计算斐波那契第 n 项long long fib(long long n) {    if (n == 0) return 0;    long long base[N][N] = {{1, 1}, {1, 0}};    long long res[N][N];    matPow(base, n - 1, res);    return res[0][0];}int main() {    long long n;    printf("请输入 n: ");    scanf("%lld", &n);    printf("Fibonacci(%lld) = %lld\n", n, fib(n));    return 0;}

关键点解析

• 单位矩阵初始化：快速幂的初始结果必须是单位矩阵（对角线为1，其余为0），相当于整数快速幂中的 res = 1。
• 位运算优化：使用 exp & 1 判断奇偶，exp >>= 1 实现除以2，效率更高。
• 避免溢出：使用 long long 类型存储中间结果，防止大数相乘溢出。

应用场景

除了斐波那契数列，快速幂优化还可用于：

• 线性递推关系（如爬楼梯、兔子繁殖）
• 图论中求路径数量（邻接矩阵的 n 次幂）
• 动态规划的状态转移优化

总结

通过本文，你已经掌握了 C语言矩阵快速幂 的基本原理与实现方法。记住，核心在于“分治”思想和矩阵乘法的正确实现。多加练习，你就能灵活运用这一强大工具解决各类算法难题！

如果你觉得这篇文章对你有帮助，不妨动手敲一遍代码，加深理解。祝你在算法之路上越走越远！