用矩阵快速幂求斐波那契数

斐波那契数列是一个递归定义的数列，其中第n个数是前两个数之和，即F(n)=F(n-1)+F(n-2)，其中F(0)=0，F(1)=1。可以使用矩阵快速幂来求斐波那契数列。

首先，将斐波那契数列的递归定义转化为矩阵乘法的形式：

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

这个矩阵乘法的形式可以通过矩阵快速幂来求解。具体来说，我们可以使用二分法来快速求幂，同时使用矩阵乘法来计算中间结果。

下面是使用C++实现的代码：

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

typedef vector<vector<long long>> matrix;

matrix multiply(matrix a, matrix b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

matrix power(matrix a, int n) {
    int m = a.size();
    matrix b(m, vector<long long>(m));
    for (int i = 0; i < m; i++) {
        b[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            b = multiply(b, a);
        }
        a = multiply(a, a);
        n /= 2;
    }
    return b;
}

long long fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    matrix a = {{1, 1}, {1, 0}};
    matrix b = power(a, n - 1);
    return b[0][0];
}

int main() {
    cout << fibonacci(0) << endl; // 0
    cout << fibonacci(1) << endl; // 1
    cout << fibonacci(2) << endl; // 1
    cout << fibonacci(3) << endl; // 2
    cout << fibonacci(4) << endl; // 3
    cout << fibonacci(5) << endl; // 5
    cout << fibonacci(6) << endl; // 8
    cout << fibonacci(7) << endl; // 13
    return 0;
}

在这个代码中，multiply函数用于计算两个矩阵的乘积，power函数用于计算矩阵a的n次方，fibonacci函数用于计算第n个斐波那契数。由于矩阵快速幂的复杂度是O(log n)，因此该算法的时间复杂度为O(log n)。