矩阵可以做数列递推。

首先你需要学会矩阵。

然后就可以构造矩阵开始矩阵快速幂递推了。

• 初始矩阵

$$\left[\begin{array}{cc} f_3\\ f_2\\ f_1 \end{array}\right]=\left[\begin{array}{cc} 1\\1\\1 \end{array}\right] $$

由于这个矩阵不符合矩阵乘法的要求，我们把它改编成单位矩阵，也就是让它的主对角线上全部为 $1$，其他位置全部为 $0$。

• 转移矩阵

$$\left[\begin{array}{cc} f_{n}\\ f_{n-1}\\ f_{n-2}\\ \end{array}\right]\times\left[\begin{array}{cc} f_{n+1}\\ f_{n}\\ f_{n-1}\\ \end{array}\right]^{-1}=\left[\begin{array}{cc} 1&0&1\\ 1&0&0\\ 0&1&0\\ \end{array}\right] $$

上代码：

using mat = matrix<mint>;
mat ans, tmp;
inline void init_tmp() {
    tmp.mat.resize(3);
    tmp.mat[0].resize(3);
    tmp.mat[1].resize(3);
    tmp.mat[2].resize(3);
    tmp.mat[0][0] = tmp.mat[0][2] = tmp.mat[1][0] = tmp.mat[2][1] = 1;
    tmp.mat[0][1] = tmp.mat[1][1] = tmp.mat[1][2] = tmp.mat[2][0] = tmp.mat[2][2] = 0;
}
inline void solve() {
    unsigned long long n;
    cin >> n;
    if (n <= 3) {
        cout << "1\n";
        return;
    }
    ans.mat.resize(3);
    ans.mat[0].resize(3);
    ans.mat[1].resize(3);
    ans.mat[2].resize(3);
    ans.mat[0][0] = ans.mat[1][1] = ans.mat[2][2] = 1;
    ans.mat[0][1] = ans.mat[0][2] = ans.mat[1][0] = ans.mat[1][2] = ans.mat[2][0] = ans.mat[2][1] = 0;
    ans = tmp.pow(n - 3);
    cout << ans.mat[1][0] << '\n';
}
int main() {
    init_tmp();
    int T;
    cin >> T;
    while (T--) solve();
}

完整代码有 22.6KB，这里不贴了。

练习：

1. 斐波那契数列
2. 广义斐波那契数列