【luogu 1962】斐波那契数列
2018-06-17 21:47:30来源:未知 阅读 ()
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
• 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 的值
输入输出样例
5
5
10
55
说明
对于 60% 的数据: n ≤ 92
对于 100% 的数据: n在long long(INT64)范围内。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 const ll Mod=1000000007; 8 ll n; 9 struct matrix{ll m[5][5];}a; 10 matrix multiply(matrix a,matrix b){ 11 matrix t; 12 for(int i=1;i<=2;i++) 13 for(int j=1;j<=2;j++){ 14 t.m[i][j]=0; 15 for(int k=1;k<=2;k++) 16 t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%Mod; 17 } 18 return t; 19 } 20 matrix fast(matrix a,ll p){ 21 matrix ans=a;p--; 22 while(p>0){ 23 if(p&1) ans=multiply(ans,a); 24 a=multiply(a,a); 25 p>>=1; 26 } 27 return ans; 28 } 29 int main(){ 30 a.m[1][2]=a.m[2][1]=a.m[2][2]=1; 31 scanf("%lld",&n); 32 matrix tmp=fast(a,n); 33 printf("%lld",tmp.m[1][2]); 34 return 0; 35 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 不一样的LCA——luoguP1852跳跳棋 2019-11-13
- LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup 2019-10-30
- 题解 Luogu P3959 【宝藏】 2019-09-23
- 题解 Luogu P1099 【树网的核】 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash