Luogu 1962 斐波那契数列（矩阵，递推）
Description
大家都知道，斐波那契数列是满足如下性质的一个数列：
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数) 请你求出 f(n) mod 1000000007 的值。
第 1 行：一个整数 n
Output
第 1 行： f(n) mod 1000000007 的值
5
Sample Output
5
Http
Luogu：https://www.luogu.org/problem/show?pid=1962
Source
递推，矩阵
解决思路
普通的斐波那契数列大家都懂，用递推方程一个一个递推就可以了，但是本题的数据范围巨大，若是用递推的方法肯定会超时，那么我们在这里介绍一下矩阵的方法。 关于矩阵的知识，请到我的这篇文章查看。 那么我们通过简单的推理可得矩阵递推方程：\[F_i=F_{i-1}*T=\begin{bmatrix} f_{i-1} & f_{i-2} \\ 0& 0 \end{bmatrix}*\begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}=\begin{bmatrix} f_i=f_{i-1}+f_{i-2} & f_{i-1} \\ 0 & 0 \end{bmatrix}\] 那么剩余的部分就是矩阵快速幂来完成了。
代码
#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;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7172026.html
相关资源：易语言斐波那契数列(递推法)源码
