题解 | 斐波那契数列

#include <bits/stdc++.h>
#define  int long long
using namespace std;

const int MOD=1e9+7;

struct kkk
{
    int m[3][3];
};

kkk operator * (const kkk& a,const kkk& b)
{
    kkk c;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            c.m[i][j]=0;
        }
    }
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int p=1;p<=2;p++)
            {
                c.m[i][j]+=(a.m[i][p]*b.m[p][j])%MOD;
                c.m[i][j]%=MOD;
            }
        }
    }
    return c;
}

kkk qmi(kkk a,int b)
{
    kkk res;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            res.m[i][j]=0;
        }
    }
    for(int i=1;i<=2;i++)
    {
        res.m[i][i]=1;
    }
    while(b)
    {
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}

signed main()
{
    int k;
    cin>>k;
    kkk x;
    x.m[1][1]=1;
    x.m[1][2]=1;
    x.m[2][1]=1;
    x.m[2][2]=0;
    kkk ans=qmi(x,k-1);
    cout<<ans.m[1][1]%MOD;
    return 0;
}