c++用矩阵快速幂的方法求斐波那契数列的第n项

斐波那契数列可以用矩阵快速幂的方法求解，时间复杂度为O(logn)。下面是使用矩阵快速幂求解斐波那契数列第n项的C++代码。

#include <iostream>
#include <vector>
using namespace std;

// 矩阵乘法
vector<vector<long long>> matrixMultiply(vector<vector<long long>>& a, vector<vector<long long>>& b)
{
    int m = a.size();
    int n = b[0].size();
    int l = b.size();
    vector<vector<long long>> c(m, vector<long long>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < l; k++)
            {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

// 矩阵快速幂
vector<vector<long long>> matrixPow(vector<vector<long long>>& a, int n)
{
    vector<vector<long long>> ans = {{1, 0}, {0, 1}}; // 单位矩阵
    while (n > 0)
    {
        if (n & 1)
            ans = matrixMultiply(ans, a);
        a = matrixMultiply(a, a);
        n >>= 1;
    }
    return ans;
}

// 斐波那契数列第n项
long long fib(int n)
{
    if (n == 0)
        return 0;
    vector<vector<long long>> a = {{1, 1}, {1, 0}};
    vector<vector<long long>> b = {{1}, {0}};
    vector<vector<long long>> c = matrixMultiply(matrixPow(a, n - 1), b);
    return c[0][0];
}

int main()
{
    int n;
    cout << "请输入n的值: ";
    cin >> n;
    cout << "斐波那契数列第" << n << "项的值为: " << fib(n) << endl;
    return 0;
}

该方法的思路是将斐波那契数列的递推式转化为矩阵形式，即

| F(n)   |   | 1 1 |   | F(n-1) |
| F(n-1) | = | 1 0 | * | F(n-2) |

然后通过矩阵快速幂的方式求出矩阵A的n-1次方，再用矩阵A的n-1次方乘以向量B，得到结果矩阵C，矩阵C的第一行第一列就是斐波那契数列的第n项的值。