题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
题目描述
请你求出 (F_n mod 10^9 + 7) 的值。
输入格式
一行一个正整数 (n)
输出格式
输出一行一个整数表示答案。
代码极其丑陋
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
ll n,mod=1e9+7;
struct E{
ll a[3][3];
};
inline E C(E t1,E t2){
E ans;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
ans.a[i][j]=0;
for(int k=1;k<=2;k++)
for(int j=1;j<=2;j++)
for(int i=1;i<=2;i++)
ans.a[i][j]=(ans.a[i][j]+t1.a[i][k]*t2.a[k][j])%mod;
return ans;
}
inline E ksm(E t,ll x){
E res;
res.a[1][1]=1;
res.a[1][2]=0;
res.a[2][1]=0;
res.a[2][2]=1;
while(x){
if(x&1)res=C(res,t);
t=C(t,t); x>>=1;
}
return res;
}
int main(){
cin>>n;
if(n==1||n==2){
cout<<1<<endl;
return 0;
}
E t;
t.a[1][1]=1;
t.a[1][2]=1;
t.a[2][1]=1;
t.a[2][2]=0;
t=ksm(t,n-2);
cout<<(t.a[1][1]+t.a[1][2])%mod;
}