洛谷P1962 斐波那契数列(矩阵快速幂)
2024-08-31 10:06:22
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
• 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 的值
输入输出样例
说明
对于 60% 的数据: n ≤ 92
对于 100% 的数据: n在long long(INT64)范围内。
感觉自己学的一直是假的矩阵快速幂。。。
辅助矩阵为
$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$
#include<cstdio>
#include<cstring>
#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int MAXN=;
const int mod=1e9+;
char buf[<<],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,k;
struct Matrix
{
int m[MAXN][MAXN];
Matrix operator * (const Matrix a)const
{
Matrix ans={};
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
return ans;
}
Matrix pow(int p)
{
Matrix ans,a=(*this);
for(int i=;i<=n;i++) ans.m[i][i]=;
while(p)
{
if(p&) ans=ans*a;
a=a*a;
// a.print();
p>>=;
}
return ans;
}
void print()
{
for(int i=;i<=n;i++,puts(""))
for(int j=;j<=n;j++)
printf("%d ",m[i][j]);
printf("*******************\n");
}
};
main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
k=read();n=;
Matrix temp,ans;
temp.m[][]=;temp.m[][]=;
temp.m[][]=;temp.m[][]=;
ans.m[][]=;ans.m[][]=;
ans.m[][]=;ans.m[][]=;
temp=temp.pow(k);
ans=ans*temp;
printf("%d",ans.m[][]);
return ;
}
最新文章
- linux的<;pthread.h>;
- SQL升级脚本实现按版本差异化升级
- POJ-2726-Holiday Hotel
- myeclipse 导入JAVA项目
- Print2flash在.NET(C#)中的使用,即文档在线预览
- INFORMATICA 的部署实施 MTP&;MTS
- Sqlite查询时间段内的数据问题解决!
- 1182-IP地址转换
- 用Y分钟学会X
- [转]Windows中的命令行提示符里的Start命令执行路径包含空格时的问题
- CentOS5.5下安装Ant
- JQuery轻量级网页编辑器 选中即可编辑
- Android 开发笔记 “Sqlite Cursor 使用”
- 高性能mysql(一)
- Javascript的异步和回调
- Spring学习笔记2——创建Product对象,并在其中注入一个Category对象
- java编程思想-第13章-某些练习题
- OO第5-7次作业总结
- require.js基本用法
- 8-GPIO复用
热门文章
- Winform开发 如何为dataGridView 添加CheckBox列,并获取选中行
- https://coderwall.com/p/7smjkq/multiple-ssh-keys-for-different-accounts-on-github-or-gitlab
- jQuery 父级,祖先,兄弟,等选择性操作
- PAT-树的同构
- css超出不换行可滑动
- linu问题集锦
- Node笔记(1)
- 我的第一个 Windows 窗口程序(1)
- JQ淡入淡出效果
- Zookeeper分布式锁解决方案具体代码