Luogu 1962 斐波那契数列（矩阵，递推）

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

5

Sample Output

5

Http

Luogu：https://www.luogu.org/problem/show?pid=1962

Source

递推，矩阵

解决思路

普通的斐波那契数列大家都懂，用递推方程一个一个递推就可以了，但是本题的数据范围巨大，若是用递推的方法肯定会超时，那么我们在这里介绍一下矩阵的方法。

关于矩阵的知识，请到我的这篇文章查看。

那么我们通过简单的推理可得矩阵递推方程：

那么剩余的部分就是矩阵快速幂来完成了。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long//注意用长整形，因为有可能会爆int

const int Mod=1000000007;

const int inf=2147483647;

class Matrix//定义矩阵

{

public:

    ll M[2][2];

    Matrix()

    {

        memset(M,0,sizeof(M));

    }

    Matrix(int Arr[2][2])//定义两个方便的矩阵初始化

    {

        for (int i=0;i<2;i++)

            for (int j=0;j<2;j++)

                M[i][j]=Arr[i][j];

    }

};

Matrix operator * (Matrix A,Matrix B)//重载乘号操作

{

    Matrix Ans;

    for (int i=0;i<2;i++)

        for (int j=0;j<2;j++)

            for (int k=0;k<2;k++)

                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;

    return Ans;

}

ll n;

int main()

{

    cin>>n;

    if (n<=2)

    {

        cout<<1<<endl;

        return 0;

    }

    n=n-2;

    int a[2][2]={{1,1},{0,0}};//初始矩阵

    int b[2][2]={{1,1},{1,0}};//即上文的T

    Matrix A(a);

    Matrix B(b);

    while (n!=0)//快速幂

    {

        if (n&1)

            A=A*B;

        B=B*B;

        n=n>>1;

    }

    cout<<A.M[0][0]<<endl;

    return 0;

}