题解 | #波斐契那数列#

类比斐波那契数列的矩阵快速幂算法即可解决这个问题。

考虑斐波那契数量的相同问题，其核心在于将 $a_n=a_{n-1}+a_{n-2},n\ge2$ 写成矩阵和向量的递推式： $v_n=Mv_{n-1}\quad n\ge2\\$ 其中， $v_n=\pmatrix{a_n\\a_{n-1}}$ ， $M=\pmatrix{1&1\\1&0}\\$

搞清楚这里是怎么做的，就可以做出本题了。两个核心问题， $v_n$ 是什么？ $M$ 是多少？

可以发现，矩阵的第一行得到的就是原始递推式，而第二行则是因为右侧向量就含有这个分量（线性相关）。类似的，我们要让本题的向量设置也是能够相邻的，因此设 $v_n=\pmatrix{a_n\\a_{n-1}\\a_{n-2}}\\$ 因此，基于本题的递推 $a_n=a_{n-1}+a_{n-3}$ 可以写出递推式

\pmatrix{a_n\\a_{n-1}\\a_{n-2}}= \pmatrix{1&0&1\\ 1&0&0\\ 0&1&0}\pmatrix{a_{n-1}\\a_{n-2}\\a_{n-3}}\quad n\ge4\\

因此，就有了 $v_n=M^{n-3}v_4=M^{n-3}\pmatrix{1\\1\\1}\\$

至此，只需要使用矩阵的快速幂即可，这只需要将一般的快速幂中的操作改成矩阵乘法即可.

提供一个模版以及AC代码：

#include <cassert>
#include <cstdint>
#include <iostream>
#include <cstring>
using namespace std;

const int64_t MOD = 1e9 + 7;

template <int N>
struct Matrix {
    int64_t mat[N][N] {};

    void init_identity() {
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i < N; i++) mat[i][i] = 1;
    }

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

template <int N>
Matrix<N> qpow(Matrix<N> a, int64_t b) {
    Matrix<N> res;
    res.init_identity();
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) res = res * a;
    }
    return res;
}

int64_t boficcina(int64_t n) {
    assert(n > 0);
    if (n <= 3) return 1;

    static const Matrix<3> m = {1, 0, 1, 1, 0, 0, 0, 1, 0};

    Matrix<3> res = qpow(m, n - 3);
    return (res.mat[0][0] + res.mat[0][1] + res.mat[0][2])%MOD;
}

void solve() {
    int n;
    cin >> n;
    cout << boficcina(n) << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
// 64 位输出请用 printf("%lld")