牛客4432题：利用矩阵快速幂将爬楼梯问题优化到O(log n)

一、问题解析

该题是经典爬楼梯问题变种：每次可跨1或2阶台阶，求到达第n阶的方法数（结果模1000000007）。传统动态规划解法时间复杂度为O(n)，而本题通过矩阵快速幂可将复杂度优化至O(log n)。

二、完整代码

class GoUpstairs {
public:// 主计算方法：输入台阶数n，返回爬楼方式数
    int countWays(int n) {
        if(n <= 0) return 0;// 边界处理
        if(n == 1) return 1;// 1阶只有1种方式
        if(n == 2) return 2;// 2阶有(1+1)或(2)两种方式
        // 构建转移矩阵
        vector<vector<long>> mat = {{1,1}, {1,0}};
        vector<vector<long>> res = matrixPower(mat, n-2);// 计算矩阵的(n-2)次幂
        //结果推导公式：f(n) = 2*res[0][0] + res[1][0]  
        return (2*res[0][0] + res[1][0]) % 1000000007;// 2x2矩阵乘法（含模运算）
    }
    
    vector<vector<long>> matrixMultiply(vector<vector<long>>& a, vector<vector<long>>& b) {
        vector<vector<long>> res(2, vector<long>(2));
        // 矩阵乘法标准公式实现
        res[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 1000000007;
        res[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 1000000007;
        res[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 1000000007;
        res[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 1000000007;
        return res;
    }
    // 矩阵快速幂算法（时间复杂度O(log p)
    vector<vector<long>> matrixPower(vector<vector<long>>& mat, int p) {
        vector<vector<long>> res = {{1,0}, {0,1}};
        while(p > 0) {
            if(p & 1) res = matrixMultiply(res, mat);// 当前二进制位为1时累乘
            mat = matrixMultiply(mat, mat);// 矩阵平方
            p >>= 1;// 右移一位
        }
        return res;
    }
};

三、核心原理

1. 递推关系：f(n) = f(n-1) + f(n-2)，可转化为矩阵形式：

   |f(n)  |   = |1 1| |f(n-1)| |f(n-1)|     |1 0| |f(n-2)|

2. 快速幂优化：通过将线性递归转化为矩阵幂运算，利用：

• 幂的二进制分解（p >>= 1）

• 平方加速（mat = matrixMultiply(mat, mat)）

3. 模运算处理：全程保持模1000000007防止整数溢出