题解 | 波斐契那数列

这个题目考察的是快速幂和线性代数，看题解有多种方法，我比较认可的是用3*3矩阵来运算。

当我直接拿到这个题目的时候，第一感觉是Dp

但是比较明显的是在这个题目里面，如果单个dp对应的是一个元素，问题不是dp会重复计算而是计算的总次数过多，状态转移不通畅，这种大数据其实适合的是使用快速幂，思路转移到直接计算，对于这个题前三项都是1,我们可以使用线性代数，把这个题目转化成快速幂问题，即f2 = M*f1（M就是转移矩阵）

每一次转移之后使得矩阵[a1,a2,a3]变成[a2,a3,a4],

求得对应的转移矩阵，最后就能将数列转化成矩阵的幂的问题，用快速幂来求m的n-3次幂，最后再乘以[a1,a2,a3]，最后返回ans即可。

线性代数的应用在这个题目里面很有趣，使用不同的数据结构来进行转化运算的逻辑，这是我们可以养成的一个意识。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

struct Matrix
{
    ll mat[3][3];
    
    Matrix()
    {
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                mat[i][j]=0;
            }
        }
    }
};

Matrix caculate(Matrix A, Matrix B)
{
    Matrix res;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                res.mat[i][j] = (A.mat[i][k]*B.mat[k][j] + res.mat[i][j])%MOD;
            }
        }
    }
    return res;
}

Matrix qpow(Matrix a, ll b)
{
    Matrix res;
    for(int i = 0; i < 3; i++) res.mat[i][i]=1;
    while(b>0)
    {
        if(b%2==1)
        {
            res = caculate(res,a);
        }
        a = caculate(a,a);
        b >>= 1;
    }
    return res;
}
void solve()
{
    ll n;
    cin >> n;
    if(n<3)
    {
        cout << 1 << endl;
        return;
    }
    Matrix m;
    m.mat[0][0]=1;m.mat[0][1]=0;m.mat[0][2]=1;
    m.mat[1][0]=1;m.mat[1][1]=0;m.mat[1][2]=0;
    m.mat[2][0]=0;m.mat[2][1]=1;m.mat[2][2]=0;
    Matrix M_n_minus_3 = qpow(m,n-3);
    ll ans = (  M_n_minus_3.mat[0][0] * 1 + 
                M_n_minus_3.mat[0][1] * 1 + 
                M_n_minus_3.mat[0][2] * 1) % MOD;
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) solve();
    return 0;
}