斐波那契数列题解：矩阵快速幂法

注意代码由人类编写但是文章由AI deepseek-r1:官网编写
博客食用更佳

题目概述

斐波那契数列是经典的递推问题，定义为：

• F(1) = F(2) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 3)

题目要求计算 F(n) 对 1e9+7 取模的值，其中 n 的范围可达 2^63-1。显然，传统递归或循环方法无法处理如此大的 n，因此我们需要更高效的算法。

思路分析

对于线性递推问题，矩阵快速幂是常用优化方法。其核心思想是将递推式转化为矩阵乘法形式，从而将时间复杂度优化至 O(logn)。

递推式的矩阵表示

假设当前状态为 [F(n-1), F(n)]，则下一状态为 [F(n), F(n+1)]。我们可以构造转移矩阵 M 使得：

[ F(n)   ]       [ F(n-1) ]
[ F(n+1) ] = M * [ F(n)   ]

通过推导，我们发现合适的转移矩阵为：

M = [[0, 1],
     [1, 1]]

验证：矩阵乘法结果为：

• 新第一元素：0F(n-1) + 1F(n) = F(n)
• 新第二元素：1F(n-1) + 1F(n) = F(n+1)

矩阵快速幂

初始状态为 [F(2), F(1)] = [1, 1]，通过计算 M 的 (n-2) 次幂，可得到 F(n)。例如：

• 当 n=5 时，计算 M^3，初始向量相乘后的第一个元素即为 F(5)=5。

代码解析

以下代码实现了矩阵快速幂算法：

#include <cstdint>
#include <vector>
#include <iostream>


using ll = int64_t;
const ll p = 1e9+7;

// 矩阵乘法
std::vector<std::vector<ll>> operator*(const std::vector<std::vector<ll>>& a, const std::vector<std::vector<ll>>& b) {
    std::vector<std::vector<ll>> res(a.size(), std::vector<ll>(b[0].size()));
    for (ll i = 0; i < a.size(); i++) {
        for (ll j = 0; j < b[0].size(); j++) {
            for (ll k = 0; k < a[0].size(); k++) {
                res[i][j] = (res[i][j] + a[i][k] * b[k][j] % p) % p;
            }
        }
    }
    return res;
}

// 快速幂
std::vector<std::vector<ll>> fp(std::vector<std::vector<ll>> b, ll e) {
    std::vector<std::vector<ll>> res(b.size(), std::vector<ll>(b[0].size()));
    // 初始化为单位矩阵
    for (ll i = 0; i < res.size(); i++) res[i][i] = 1;
    while (e) {
        if (e & 1) res = res * b;
        b = b * b;
        e >>= 1;
    }
    return res;
}

int main() {
    ll n;
    std::cin >> n;
    if (n <= 2) {
        std::cout << 1 << '\n';
        return 0;
    }
    n -= 2;
    std::vector<std::vector<ll>> base = {{0, 1}, {1, 1}};
    base = fp(base, n);
    std::cout << (base[0][1] + base[1][1]) % p << '\n';
    return 0;
}

关键步骤说明

1. 矩阵构造：转移矩阵 base 初始化为 [[0,1],[1,1]]。
2. 快速幂计算：对 base 进行 (n-2) 次幂运算，结果矩阵的 base[0][1] 和 base[1][1] 之和即为 F(n)。
3. 模运算处理：在矩阵乘法中每一步都进行取模，防止数值溢出。

复杂度分析

• 时间复杂度：O(logn)，快速幂的二分思想使得矩阵乘法次数为对数级别。
• 空间复杂度：O(1)，矩阵大小固定为 2x2。

总结

矩阵快速幂法将递推问题转化为矩阵运算，极大优化了时间复杂度，适用于大数情况。该方法可扩展至其他线性递推问题，关键在于构造合适的转移矩阵。