题解 | #波斐契那数列#

显然是矩阵快速幂。

显然有初始矩阵：

$\begin{bmatrix} a_x & a_{x-1} & a_{x-2} \end{bmatrix}$

我们要找到一个矩阵 $G$ ，使得 $\begin{bmatrix} a_x & a_{x-1} & a_{x-2} \end{bmatrix} G=\begin{bmatrix} a_{x+1} & a_x & a_{x-1} \end{bmatrix}$

容易得到：

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

然后直接矩阵快速幂即可，代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
struct martix{
    ll x,y;vector<vector<ll>> a;
    martix(ll w,ll h){
        a.resize(w);
        for(ll i=0;i<w;i++) a[i].resize(h);
        x=w,y=h;
    }
    friend martix operator*(martix a,martix b){
        martix c(a.x,b.y);
        for(ll i=0;i<c.x;i++){
            for(ll j=0;j<c.y;j++){
                for(ll k=0;k<a.y;k++){
                    c.a[i][j]+=a.a[i][k]*b.a[k][j]%mod;
                    c.a[i][j]%=mod;
                }
            }
        }
        return c;
    }
}a(1,3),b(3,3);
martix qpow(martix s,martix t,ll b){
    martix res=s;
    while(b){
        if(b&1){
            res=res*t;
        }
        t=t*t,b>>=1;
    }
    return res;
}
void solve(){
    ll x;cin>>x;
    if(x<=3){
        cout<<1<<endl;
    }else{
        martix ans=qpow(a,b,x-3);
        cout<<ans.a[0][0]<<endl;
    }
}
int main(){
    a.a[0][0]=a.a[0][1]=a.a[0][2]=1;
    b.a[0][0]=b.a[0][2]=1,b.a[1][0]=1,b.a[2][1]=1;
    ll T;cin>>T;
    while(T--) solve();
}