洛谷 P1962:斐波那契数列 ← 矩阵快速幂
【题目来源】
https://www.luogu.com.cn/problem/P1962
【题目描述】
大家都知道,斐波那契数列是满足如下性质的一个数列:F1=1,F2=1,Fn=Fn-1+Fn-2,n≥3。
请你求出 Fn mod 10^9+7 的值。
【输入格式】
一行一个正整数 n。
【输出格式】
输出一行一个整数表示答案。
【输入样例】
10
【输出样例】
55
【数据范围】
对于 60% 的数据,1≤n≤92;
对于 100% 的数据,1≤n<2^63。
【算法分析】
【算法代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2;
const int MOD=1e9+7;
LL n;
struct Matrix {
LL m[maxn][maxn];
Matrix() { //Constructor in struct
memset(m,0,sizeof m);
}
};
Matrix mul(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;
return ans;
}
void fastPow(LL n) {
Matrix base,t;
base.m[0][0]=1,base.m[0][1]=1;
base.m[1][0]=1,base.m[1][1]=0;
t.m[0][0]=1,t.m[0][1]=1; //f[1]=1,f[2]=1
while(n) {
if(n&1) t=mul(t,base);
base=mul(base,base);
n=n>>1;
}
cout<<t.m[0][0]<<endl;
}
int main() {
cin>>n;
if(n==1) cout<<"1"<<endl;
else fastPow(n-2);
return 0;
}
/*
in:
10
out:
55
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143227091
https://mp.weixin.qq.com/s/Az68VdFnRDUZ8vczKwRB4g
https://www.cnblogs.com/zxsoul/articles/14407155.html