首先我们抛出一个问题，如何快速求出 ？

1.整数幂运算

整数幂运算公式准备：
① 同底数幂相乘：
② 幂的乘方：
③ 积的乘方：
④ 同底数幂相除：

上面问题可转化为下图：

设 ，则 对应的二进制为1011


要计算 ，即要计算出
根据上面公式有： ，即
所以循环按顺序计算 ， 得 , 得 ...

代码实现-整数幂运算

int pow(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) {
            ret *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ret;
}

2.矩阵幂运算

矩阵运算公式准备：
① 乘法结合律：
② 乘法左分配律：
③ 乘法右分配律：
④ 对数乘的结合性： ）
⑤ 转置：
⑥ 矩阵乘法一般不满足交换律

代码实现-矩阵乘法

void multiMatrix(int a[][N], int b[][N]) {
    int tmp[N][N] = {0}, i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            for (int k = 0; k < N; k++) {
                tmp[i][j] += a[i][k] * b[k][j];
            }

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            a[i][j] = tmp[i][j];
        }
}

代码实现-矩阵幂运算

void powMatrix(int a[][N], int b, int ret[][N]) {
    memset(ret, 0, sizeof(int) * N * N);
    for (int i = 0; i < N; i++) {
        ret[i][i] = 1;
    }

    while (b) {
        if (b & 1) {
            multiMatrix(ret, a);
        }
        multiMatrix(a, a);
        b >>= 1;
    }
}

3.斐波那契数列

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21......
该数列从第3项开始，每一项都等于前两项之和，即

代码实现-递归求解

int solve(int step) {
    if (step == 0 || step == 1) {
        return 1;
    }
    return solve(step - 1) + solve(step - 2);
}

代码实现-递推求解

f[0] = 1; f[1] = 1;
for (int i = 2; i < N; i++){
    f[i] = f[i - 1] + f[i - 2]
}
cout << f[N - 1] << endl;

3.1.矩阵递推

斐波那契数列递推公式很简单，但数据很大时，效率就比较低，因为递推是 复杂度。
通过矩阵公式变换可将加法变为乘法
如下将递推公式放入矩阵：

假设： 则:

3.2.Fibonacci数列变种

如果现在要对Fibonacci数列的前N项求和，又该如何变换成矩阵乘法呢？
数列前 项和
其实方法是一样的，关键在于找出递推矩阵，如下：

4.普通递推矩阵变换

如何快速找出递推矩阵呢？
将递推式左右两边先写入矩阵，然后构造A矩阵，根据现有项补全剩余项。
具体步骤如下图所示：

步骤如下
①将递推公式写入红色位置
②反推蓝色位置
③补全绿色位置，即为新的递推项
④补全 矩阵剩余的值

例1：
例1递推矩阵如下：

例2：
例2递推矩阵如下：

这里就不举更多的例子了，方法是一样的，可以自己随便写几个公式，然后按照上面的方法推导。