思路

三阶斐波那契数列满足

$$f(n)=f(n-1)+f(n-2)+f(n-3),\qquad f(1)=1,\ f(2)=1,\ f(3)=2$$

$n$ 可以很大，逐项递推会超时，因此用矩阵快速幂加速。

取行向量与转移矩阵

$$G(n)=\begin{bmatrix} f(n-2) & f(n-1) & f(n) \end{bmatrix},\qquad A=\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$$

先验证 $G(n+1)=G(n)\cdot A$：右乘 $A$ 的第 $1$ 列得到 $f(n-1)$，第 $2$ 列得到 $f(n)$，第 $3$ 列得到 $f(n-2)+f(n-1)+f(n)=f(n+1)$，正好是新的窗口。

于是 $G(n)=G(1)\cdot A^{\,n-1}$，其中 $G(1)=[f(-1),f(0),f(1)]$。由递推式外推可得 $f(0)=f(-1)=0$，所以 $G(1)=[0,0,1]$。

因此对每个询问只需计算 $[0,0,1]\cdot A^{n-1}$，答案就是结果的第 $3$ 个分量（代码中先对单位矩阵求 $A^{n-1}$，再左乘初始行向量，等价于同一件事）。

实现细节：

• 矩阵乘法对 $10^9+7$ 取模，用 long long（#define int long long）防止中间乘积溢出。
• 快速幂按二进制从低位到高位，维护累乘矩阵 e（初值为单位矩阵）和底数 a。
• 指数为 $0$ 时（即 $n=1$）e 保持单位矩阵，结果正确。

复杂度： 每次询问 $O(3^3\log n)=O(\log n)$，与 $t$ 个询问合计 $O(t\log n)$；矩阵固定为 $3\times3$，空间 $O(1)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9+7;

// 通用的小矩阵结构体，支持乘法，元素对 mod 取模
struct matrix
{
    int n;
    int m;
    vector<vector<int>>a;

    matrix(int N, int M){
        n = N, m = M;
        a.assign(N, vector<int>(M, 0));
    }

    // 用二维数组初始化矩阵，维度不匹配时直接忽略
    void set_matrix(vector<vector<int>> ma){
        int n1 = ma.size();
        int m1 = (n1==0?0:ma[0].size());

        if(n1!=n or m1!=m){return;}

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j] = ma[i][j];
            }
        }
    }

    // 矩阵乘法：维度不匹配时原样返回传进来的矩阵（正常逻辑不会走到）
    matrix operator*(const matrix x)const{
        int n1 = x.n, m1 = x.m;
        if(m != n1){return x;}
        matrix res(n, m1);

        for(int i=0;i<n;i++){
            for(int j=0;j<m1;j++){
                for(int k=0;k<m;k++){
                    res.a[i][j] += a[i][k]*x.a[k][j];
                    res.a[i][j] %= mod;   // 每步取模，防止溢出
                }
            }
        }

        return res;
    }
};

void go(){
    int n;cin>>n;
    matrix a(3, 3), ori(1, 3);
    // 转移矩阵 A
    a.set_matrix({{0, 0, 1},
                  {1, 0, 1},
                  {0, 1, 1}});
    // 初始行向量 G(1) = [f(-1), f(0), f(1)]
    ori.set_matrix({{0, 0, 1}});

    // 单位矩阵，用于累乘 A^(n-1)
    matrix e(3, 3);
    e.set_matrix({{1, 0, 0},
                  {0, 1, 0},
                  {0, 0, 1}});

    int b = n-1;                     // 指数为 n-1
    while (b)
    {
        if(b&1){
            e = e*a;                 // 当前二进制位为 1，乘进结果
        }
        a = a*a;                     // 底数平方
        b /= 2;
    }

    ori = ori*e;                     // 左乘结果：G(n) = G(1) * A^(n-1)

    int ans = ori.a[0][2];           // 第三个分量就是 f(n)
    ans = (ans+mod)%mod;
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin >>_;                         // 多组询问
    while(_--){
        go();
    }
    return 0;
}