洛谷P1962 斐波那契数列题解
2024-08-30 10:10:02
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入格式
·第 1 行:一个整数 n
输出格式
第 1 行: f(n) mod 1000000007 的值
输入输出样例
输入 #1 复制
5
输出 #1 复制
5
输入 #2 复制
10
输出 #2 复制
55
说明/提示
对于 60% 的数据: n ≤ 92
对于 100% 的数据: n在long long(INT64)范围内。
解析:
\(\displaystyle \begin{array}{{>{\displaystyle}l}}
\ 现在我需要求的矩阵是:\\
\begin{bmatrix}
f[ i]\\
f[ i-1]
\end{bmatrix}\\
根据题目中给出的条件:f[ i] =f[ i-1] +f[ i-2]\\
下一步求f[ i+1]\\
所以求初始矩阵为\\
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\\
对初始矩阵进行矩阵快速幂然后输出a[ 1][ 1]
\end{array}\)
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#define re register
#define Max 200000012
#define int long long
int n;
const int mod=1000000007;
struct Mat {
int a[3][3];
Mat() {memset(a,0,sizeof a);}
inline void build() {
memset(a,0,sizeof a);
for(re int i = 1 ; i <= 2 ; ++ i) a[i][i]=1;
}
};
Mat operator*(Mat &a,Mat &b)
{
Mat c;
for(re int k = 1 ; k <= 2 ; ++ k)
for(re int i = 1 ; i <= 2 ; ++ i)
for(re int j = 1 ; j <= 2 ; ++ j)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
return c;
}
Mat a;
Mat quick_Mat(int x)
{
Mat ans;ans.build();
while(x) {
if((x&1)==1) ans = ans * a;
a = a * a;
x >>= 1;
}
return ans;
}
signed main()
{
scanf("%lld",&n);
a.a[1][1]=1;a.a[1][2]=1;
a.a[2][1]=1;Mat b;
b.a[1][1]=1;b.a[2][1]=1;
if(n>=1 && n<=2) {
printf("1");return 0;
}
Mat ans=quick_Mat(n-2);
ans=ans*b;
printf("%lld",ans.a[1][1]);
return 0;
}
最新文章
- C# 条件编译
- java DOM4J 读取XML
- tail 命令 查看Tomcat目录下日志的最后几行的方法
- 数往知来 ASP.NET 模拟服务器:服务端_静态页面_动态页面的响应<;十七>;
- 《Entity Framework 6 Recipes》中文翻译——第九章EntityFramework在N层架构程序中的应用(七)
- arcgis python 获得所有的工具名称
- app图标和启动页设置
- Drawer_layout 关闭滑动视图
- 简单的CSS网页布局--一二列布局
- JQUERY UI DOWNLOAD
- 如何写一个SSH项目(三)如何进行交互的
- 从一个word文件中读取所有的表格和标题(2)
- 程序设计之---单例模式VS静态方法
- Windows Internals 笔记——内核对象
- 【Spark2.0源码学习】-7.Driver与DriverRunner
- win10 文件扩展名的更改
- Python问题之“NameError: name 'reload' is not defined”
- 前端文档汇总(含代码规范、开发流程、知识分享,持续更新) front-end-Doc
- 剑指offer.找出数组中重复的数字
- 【AtCoder】CODE FESTIVAL 2017 Final
热门文章
- 【java】java删除文件delete和deleteOnExit 方法的区别,为什么调用deleteOnExit无效?
- NETCore使用带有权限验证的Swagger
- Windows服务的安装及配合定时器编写简单的程序
- Android 权限的一些细节
- C# 查看系统进程
- HTML不换行,多余用省略号代替
- Android studio module生成jar包,module中引用的第三方库没有被引用,导致java.lang.NoClassDefFoundError错误。
- spring boot 的request.getServletContext().getRealPath路径获取问题
- 自制微擎AI面相识别算术阈值
- 排序算法的c++实现——归并排序