题解

矩阵板子题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
struct M
{
    int a[2][2];
    M(){memset(a,0,sizeof a);}
};
M mul(M x,M y)
{
    M z;
    for(int i=0;i<2;i++)
        for(int k=0;k<2;k++)
            for(int j=0;j<2;j++)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
    return z;
}
M qpow(M b,int e)
{
    M r;
    r.a[0][0]=r.a[1][1]=1;
    while(e)
    {
        if(e&1)r=mul(r,b);
        b=mul(b,b);
        e>>=1;
    }
    return r;
}
signed main()
{
    int n;
    cin>>n;
    if(n<=2)
    {
        cout<<1;
        return 0;
    }
    M T;
    T.a[0][0]=1;T.a[0][1]=1;
    T.a[1][0]=1;T.a[1][1]=0;
    M r=qpow(T,n-1);
    cout<<r.a[0][0]%MOD;
    return 0;
}