lg1962

发表于 | 分类于 ， ， | 阅读数 次

链接:lg1962

Description

  • 大家都知道，斐波那契数列是满足如下性质的一个数列：
    • f(1) = 1
    • f(2) = 1
    • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
  • 请你求出 f(n) mod 1000000007 的值。

    Input

  • 第 1 行：一个整数 n

    Output

  • 第 1 行： f(n) mod 1000000007 的值

    Sample Input

    1: 5
    2: 10

    Sample Output

    1: 5
    2: 55

    题解

  • F(n)=F(n-1)+F(n-2)
  • 构造T：{1,1 和A(n-1){F(n-1)
  • 1,0} F(n-2)}
  • 乘起来就得到F(n)，然后这就是个等比数列 然后就可以用快速幂了(手动滑稽)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int p=1000000007;
struct mat{
    ll a[2][2];
};
ll n;
mat T={1,1,1,0};

void readin(){
    ios::sync_with_stdio(false);
    cin>>n;
}

mat mul(mat x,mat y){
    mat ans={0};
    rep(i,0,1)rep(j,0,1)rep(k,0,1){
        ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%p;
    }
    return ans;
}

void solve(){
    n-=2;
    mat ans={0,1,0,1};
    while(n){
        if(n&1)ans=mul(T,ans),n--;
        T=mul(T,T);
        n>>=1;
    }
    cout<<ans.a[0][1];
}

int main(){
    readin();
    if(n==1||n==2)cout<<1<<endl;
    else solve();
    return 0;
}