【历年真题】斐波那契数列logn做法
真题 数列 斐波 那契 做法 历年
2023-09-14 09:03:43 时间
描述
【题解】
用矩阵乘法加速递推 [0 1] [1 1] * [f[n-1]] [f[n-2]] = [f[n-1]] [f[n]] 求A矩阵的n-2次幂然后再乘B矩阵。 结果矩阵中的第二行第一列就是f[n]的结果了【代码】
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N = 100;
const long long MOD = 1e9+7;
const int G = 2;
struct abc{
ll v[G+10][G+10];
void print(){
for (int i = 1;i <= G;i++)
{
for (int j = 1;j <= G;j++)
printf("%I64d ",v[i][j]);
puts("");
}
puts("");
}
void E(){
memset(v,0,sizeof v);
for (int i = 1;i <= G;i++) v[i][i]=1;
}
void O(){
memset(v,0,sizeof v);
}
abc operator * (const abc b) const{
abc temp;temp.O();
for (int i = 1;i <= G;i++)
for (int j = 1;j <= G;j++){
ll sum = 0;
for (int k = 1;k<= G;k++){
sum=(sum+v[i][k]*b.v[k][j])%MOD;
}
temp.v[i][j] = sum;
}
return temp;
}
abc operator ^(int n)const{
abc x;x.E();
abc y;memcpy(y.v,v,sizeof(v));
while (n>0){
if (n&1) x=x*y;
y = y*y;
n/=2;
}
return x;
}
};
abc a,b;
int n;
int main(){
scanf("%d",&n);
a.O();
a.v[1][1] = 0;a.v[1][2] = 1;
a.v[2][1] = 1;a.v[2][2] = 1;
b.O();
b.v[1][1] = 1;b.v[2][1] = 1;
if (n<=2){
printf("%d\n",1);
}else{
a = a^(n-2);
a = a*b;
printf("%I64d\n",a.v[2][1]);
}
return 0;
}
相关文章
- 杭电2018年计算机复试真题
- 杭电2015年计算机复试真题
- C/C++常见面试知识点总结附面试真题—-20220326更新
- [蓝桥杯][2014年第五届真题]波动数列(DP 简洁)
- Python入门习题(40)——CCF CSP认证考试真题:报数游戏「建议收藏」
- React-Hooks怎样封装防抖和节流-面试真题
- 网易2017春招笔试真题编程题集合题解
- 每天一道大厂SQL题【Day11】微众银行真题实战(一)
- 【题解】蓝桥杯2022年第十三届省赛(第二场)真题-求和
- 系统分析师2022真题试卷概念一
- 系统分析师真题2020试卷相关概念一
- 在面试中如何巧妙的展现架构能力?附200道面试真题+100例经典架构案例拆解 | 极客时间
- SQL Server真题考验你的考试技能(sqlserver真题)
- 真题来自一线大厂的Redis面试真题面试挑战重重(一线大厂redis面试)
- 考试为Oracle DBA考古真题考查学习进入期末落下帷幕(oracle dba期末)