当前位置:网站首页>洛谷 P1962 斐波那契数列

洛谷 P1962 斐波那契数列

2021-07-27 14:55:45 雀食蟀

题目背景

大家都知道,斐波那契数列是满足如下性质的一个数列:

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式:

 

·第 1 行:一个整数 n

 

输出格式:

 

第 1 行: f(n) mod 1000000007 的值

 

输入输出样例

输入样例#1:
5
输出样例#1:
5
输入样例#2:
10
输出样例#2:
55

说明

对于 60% 的数据: n ≤ 92

对于 100% 的数据: n在long long(INT64)范围内。

 

问题转化为求

矩阵

1 1

1 0 的n-2次方

至于为什么转化为这个矩阵 点击就送传奇宝箱 

#include <cstdio>
#define mod 1000000007
typedef long long LL;
LL n;
struct node
{
    LL a[4][4];
    inline node operator*(node b)const
    {
        node c;
        for(int i=1;i<=2;++i)
            for(int j=1;j<=2;++j)
            {
                c.a[i][j]=0;
                for(int k=1;k<=2;++k)
                    c.a[i][j]+=a[i][k]*b.a[k][j],c.a[i][j]%=mod;
            }
        return c;
    }
}base,ans;
int main()
{
    scanf("%lld",&n);n-=2;
    if(n+2==1||n+2==2) {printf("1\n");return 0;}
    base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
    ans.a[1][1]=ans.a[1][2]=ans.a[2][1]=1;
    for(;n;n>>=1,base=base*base) if(n&1) ans=ans*base;
    printf("%lld\n",ans.a[1][1]);
    return 0;
}

 

我们都在命运之湖上荡舟划桨,波浪起伏着而我们无法逃脱孤航。但是假使我们迷失了方向,波浪将指引我们穿越另一天的曙光。
 
 
 
 

版权声明
本文为[雀食蟀]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15314810/3197163