普适

在算法学习中，快速幂是一个非常基础且重要的技巧。它不仅可以解决大数取模问题，还能为后续的矩阵快速幂打下基础。下面我们先来回顾一下快速幂的实现。

/*
 * 函数名称: QuickMi
 * 功能描述: 计算 (a^b) mod p 的值，采用快速幂算法（也称二进制快速幂）。
 *
 * 参数说明:
 *   - int a: 底数
 *   - int b: 指数
 *   - int p: 模数
 *
 * 返回值:
 *   - 返回 (a^b) % p 的结果
 *
 * 实现原理:
 *   1. 快速幂算法通过“平方取幂”的方式，将指数 b 的二进制逐位拆解，
 *      在每次循环中判断 b 的最低位是否为 1：
 *        - 如果是 1，则将当前底数乘到结果中。
 *        - 每次迭代后，底数自乘（平方），指数右移（除以 2）。
 *   2. 整个过程保证了时间复杂度从 O(b) 降低到 O(log b)。
 *   3. 在每一步都对结果和底数取模，避免溢出并保持结果在 [0, p-1]。
 *
 * 使用场景:
 *   - 大数计算：避免因幂运算过大导致数据溢出。
 *   - 模运算场景：如密码学、组合数计算、数论问题等。
 */
 
int QuickMi(int a, int b, int p)
{
    int res = 1;          // 初始化结果为 1
    while(b)              // 当指数 b > 0 时继续循环
    {
        if(b & 1)         // 如果 b 的当前最低位是 1
            res = res * a % p;  // 将当前底数乘到结果上，并取模
        b >>= 1;          // 指数右移一位（相当于 b / 2）
        a = a * a % p;    // 底数平方，并取模
    }
    return res;           // 返回最终结果
}

Acwing 例题 链接

拓展–矩阵（斐波那契数列）

快速幂的思想并不仅仅应用于整数指数运算。当我们将其扩展到矩阵运算时，便能解决更多复杂问题。一个经典案例就是：如何快速求解斐波那契数列的第 n 项？

矩阵乘法

在进入矩阵快速幂之前，我们先复习一下矩阵乘法的基本操作。理解这个过程是后续掌握矩阵快速幂的关键。

/*
 * 函数名称: mul
 * 功能描述: 实现矩阵乘法 C = A × B
 *
 * 参数说明:
 *   - int n: 矩阵 A 的行数
 *   - int m: 矩阵 A 的列数（同时也是矩阵 B 的行数）
 *   - int p: 矩阵 B 的列数
 *   - int A[][maxn]: 左矩阵 A，大小 n × m
 *   - int B[][maxn]: 右矩阵 B，大小 m × p
 *   - int C[][maxn]: 结果矩阵 C，大小 n × p
 *
 * 返回值:
 *   - 无（结果保存在 C 中）
 *
 * 实现原理:
 *   - 矩阵乘法公式:
 *       C[i][j] = Σ (A[i][k] * B[k][j])   , k = 0..m-1
 *   - 外层循环遍历矩阵 C 的行与列，
 *     内层循环累加对应乘积，得到 C[i][j]。
 *
 * 注意事项:
 *   - 时间复杂度 O(n × m × p)，
 *     在大规模矩阵运算时可能性能较低。
 *   - 若需要防止溢出或取模，可在累加时加上 %mod。
 */

void mul(int n, int m, int p, int A[][maxn], int B[][maxn], int C[][maxn]) {
    for(int i = 0; i < n; i++) {          // 遍历结果矩阵的每一行
        for(int j = 0; j < p; j++) {      // 遍历结果矩阵的每一列
            C[i][j] = 0;                  // 初始化结果元素
            for(int k = 0; k < m; k++) {  // 遍历 A 的列 / B 的行
                C[i][j] += A[i][k] * B[k][j]; 
            }
        }
    }
}

矩阵乘法的公式可以写成：

$$ C[i][j] = \sum_{k=0}^{m-1} A[i][k] \times B[k][j] $$

接下来，让我们看看斐波那契数列与矩阵的关系。

$$ \overset{\Lambda_{n-1}}{\begin{bmatrix} a_{n-1} & a_{n} \\ 0 & 0 \end{bmatrix}} \times \overset{F}{\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}} = \overset{\Lambda_{n}}{\begin{bmatrix} a_{n} & a_{n+1} \\ 0 & 0 \end{bmatrix}} $$

斐波那契与矩阵快速幂

通过上面的矩阵关系，我们可以将斐波那契数列的递推公式转化为矩阵乘法问题。利用快速幂思想，我们可以在 O(log n) 的复杂度内计算 F(n)。

/*
 * 函数名称: mul
 * 功能描述: 计算两个 2x2 矩阵的乘法，并对结果取模。
 *
 * 参数说明:
 *   - int a[][2]: 输入矩阵 A，同时存放结果
 *   - int b[][2]: 输入矩阵 B
 *
 * 实现原理:
 *   - 使用三重循环进行矩阵乘法。
 *   - 结果矩阵 c 初始化为 0，每次相乘后加到 c[i][j] 上。
 *   - 取模操作保证结果不溢出（模数通过全局变量 mod 提供）。
 *   - 结果通过 memcpy 拷贝回矩阵 a。
 */

void mul(int a[][2], int b[][2])
{
    int c[2][2] = {0};  // 临时结果矩阵，初始化为 0
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    memcpy(a, c, sizeof c); // 把结果复制回 a
}

/*
 * 函数名称: fib
 * 功能描述: 使用矩阵快速幂计算斐波那契数列的第 n 项。
 *
 * 参数说明:
 *   - int n: 要求的斐波那契数列项 (从 F(1) 开始)
 *
 * 返回值:
 *   - 返回第 n 项斐波那契数，取模 mod。
 *
 * 实现原理:
 *   - 利用矩阵关系:
 *   - 用快速幂思想，每次判断 n 的二进制最低位:
 *       如果是 1，则把当前基矩阵 f 乘到结果矩阵 a 上。
 *   - 每次迭代后，基矩阵 f 自身平方。
 *   - 初始结果矩阵 a 设为单位形式 (此处通过 {0,1,0,0} 巧妙初始化)。
 *   - 最终返回 a[0][0] 即为 F(n)。
 */

int fib(int n)
{
    int a[2][2] = {0, 1, 0, 0}; // 结果矩阵 (类似单位矩阵的变形)
    int f[2][2] = {0, 1, 1, 1}; // 基础矩阵 (构造斐波那契递推)
    while(n)
    {
        if(n & 1) mul(a, f); // 若当前位为 1，则累乘 f
        n >>= 1;             // 指数右移一位
        mul(f, f);           // 基础矩阵平方
    }
    return a[0][0];          // 返回结果
}