大家都知道,斐波那契数列是满足如下性质的一个数列:
Fn?={1 (n≤2)
Fn−1?+Fn−2? (n≥3)?
请你求出 Fn mod 10^9 + 7的值。
一行一个正整数 n
输出一行一个整数表示答案。
5
5
10
55
【数据范围】
对于 60% 的数据,1≤n≤92;
对于 100% 的数据,1}1≤n<2^63。
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long mod=1e9+7;
struct Matrix
{
int m[4][4];//因为本题是斐波那契数列,只需要用到2,所以开4(无所谓)
};//定义矩阵结构体
Matrix ans,res,a;
//矩阵乘法
Matrix Mul(Matrix A,Matrix B)
{
Matrix tmp;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
tmp.m[i][j]=0;//全部初始化为0,因为矩阵乘法是要累加的
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
tmp.m[i][j]+=A.m[i][k]*B.m[k][j];//矩阵乘法定义
return tmp;
}
//矩阵快速幂
void quickpower(int N)
{
ans.m[1][1]=1,ans.m[1][2]=1,ans.m[2][1]=0,ans.m[2][2]=0;//这里的初始化,也是应题,斐波那契数列,前两项是1,1;而剩下的位置补0,对结果是没有影响的。这里必须要用ans去一个个乘res,而不能把res的N次方算出来再去求ans乘以res^N,因为矩阵没有交换律结合律,那样会改变结果
while(N)
{
if(N&1)
ans=Mul(ans,res);
res=Mul(res,res);
N=N>>1;
}//快速幂的另一种写法:当还有指数的时候(指数不为0):如果N%2==1(N&1),那么就需要多乘一个res矩阵;如果是偶数,那么就不用多乘。下一步是让res平方,举个例子:2^9=2*2*2*2*2*2*2*2*2,那么ans=2,剩下的是8个2相乘,就相当于4个2^2相乘,所以指数除以2(N>>1),res平方
}
int main()
{
long long x;
cin>>x;
if(x==1||x==2)
{
cout<<1;
return 0;
}//如果是前两个,直接输出
res.m[1][1]=1,res.m[1][2]=1,res.m[2][1]=1,res.m[2][2]=0;//不多解释,凑出这个,和Fn,Fn-1相乘可以得出Fn+1,Fn
quickpower(x-2);//从第三项开始运用公式,所以减2.比如说F3,是F2乘一次res得来的,所以是x-2
cout<<ans.m[1][1]%mod;//输出结果
}
对于刚学矩阵快速幂的蒟蒻我来说,真的太难了,而且写了半天最后才40.还需要改进啊
原文:https://www.cnblogs.com/57xmz/p/12556449.html