题解 | #斐波那契数列#

其实直接递推就行了，但是由于一开始没看清范围还写了个矩阵快速幂，代码：

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