题解 | #波斐契那数列#

问题分析

对于给定的递推数列 $a_x = a_{x-1} + a_{x-3}$ （ $x \ge 4$ ），其本质是一个高阶（三阶）常系数线性齐次递推关系。

时间复杂度瓶颈：查询数量 $T \le 100$ ，项数 $n \le 2 \times 10^9$ 。若采用传统的动态规划进行 $O(n)$ 的线性递推，单次查询最高将达到 $2 \times 10^9$ 次运算，总运算量达 $2 \times 10^{11}$ ，这会引发严重的超时。
空间复杂度限制：由于 $n$ 极大，若尝试采用空间换时间（预处理并存储所有结果），将需要约 $8\text{GB}$ 的连续内存（假设使用 32 位整型），这必然导致内存超限。
数据溢出风险：由于数列呈指数级变大，且要求对 $10^9+7$ 取模，在任何涉及加法或乘法的算术操作中，不仅最终结果需要取模，中间运算过程也会迅速突破 32 位整型的上限，必须在所有子操作中严格应用模运算律。

算法：矩阵快速幂

针对超大项数的常系数线性递推问题，矩阵快速幂是唯一的工业级标准解法。它将线性的递推过程转化为矩阵的幂运算，从而利用“快速幂”算法的倍增思想，将线性时间复杂度降维至对数时间复杂度。

状态空间的矩阵化

设状态列向量 $V_i = \begin{bmatrix} a_i \\ a_{i-1} \\ a_{i-2} \end{bmatrix}$ ，我们需要构造一个状态转移矩阵 $M$ ，使得 $V_i = M \cdot V_{i-1}$ 。

根据递推公式：

$a_i = 1 \cdot a_{i-1} + 0 \cdot a_{i-2} + 1 \cdot a_{i-3}$
$a_{i-1} = 1 \cdot a_{i-1} + 0 \cdot a_{i-2} + 0 \cdot a_{i-3}$
$a_{i-2} = 0 \cdot a_{i-1} + 1 \cdot a_{i-2} + 0 \cdot a_{i-3}$

由此抽离出 $3 \times 3$ 的转移矩阵 $M$ ：

M = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}

状态转移通项

已知基础状态为 $x \in \{1,2,3\}$ 时的值，提取基础列向量 $V_3$ ：

V_3 = \begin{bmatrix} a_3 \\ a_2 \\ a_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}

根据矩阵的结合律，对于任意 $n \ge 4$ ，可推导出状态列向量通式：

V_n = M^{n-3} \cdot V_3

目标值 $a_n$ 即为结果列向量 $V_n$ 的第一行元素。

复杂度分析

时间复杂度： $O(T \cdot k^3 \log n)$ 。其中 $k$ 为矩阵维度（本题 $k=3$ ）。两个 $k \times k$ 矩阵相乘耗时 $O(k^3)$ ，指数递减需 $\log_2(n)$ 步。完全满足 1 秒执行完毕的性能要求。
空间复杂度： $O(k^2)$ 。整个计算生命周期内仅需维护常量个 $3 \times 3$ 的矩阵，空间开销可忽略不计。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr int MOD = 1e9 + 7;

struct Matrix {
    array<array<ll, 3>, 3> data{};

    // 单位矩阵
    static Matrix identity() {
        Matrix res;
        for (int i = 0; i < 3; i++)
            res.data[i][i] = 1;
        return res;
    }

    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 3; i++) {
            for (int k = 0; k < 3; k++) {
                if (data[i][k] == 0)
                    continue;
                for (int j = 0; j < 3; j++) {
                    res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

template <typename T>
T power(T base, ll exp) {
    T res = T::identity();
    while (exp > 0) {
        if (exp & 1)
            res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;

    if (n <= 3) {
        cout << 1 << "\n";
        return;
    }

    Matrix T;
    T.data = {{
            {1, 0, 1},
            {1, 0, 0},
            {0, 1, 0}
        }
    };

    auto res = power(T, n - 3);

    ll ans = 0;
    for (int j = 0; j < 3; j++) {
        ans = (ans + res.data[0][j]) % MOD;
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}