首页 > 代码库 > 洛谷P1962 斐波那契数列
洛谷P1962 斐波那契数列
P1962 斐波那契数列
题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列：
• 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)范围内。
/* 矩阵快速幂重载运算符计算*/#include <cstdio>#define Mod 1000000007#define Max 2struct Martix_Data { long long data[Max][Max]; void Prepare () { data[0][0] = 1; data[0][1] = 1; data[1][0] = 1; data[1][1] = 0; } Martix_Data operator*(const Martix_Data &now) const { Martix_Data res; for (int i = 0; i < Max; i ++) for (int j = 0; j < Max; j ++) { res.data[i][j] = 0; for (int k = 0; k < Max; k ++) res.data[i][j] = (res.data[i][j] + data[i][k] * now.data[k][j]) % Mod; } return res; }};Martix_Data operator ^ (Martix_Data &now, long long P) { Martix_Data res; res.Prepare (); if (P == 1) res.data[0][0] = 1; else if (P == 0) res.data[0][0] = 0; else{ P-=2; while(P){ if (P & 1) res = res * now; now = now * now; P>>=1; } } return res;}long long N;int main () { scanf("%lld",&N); Martix_Data Answer; Answer.Prepare (); Answer = Answer ^ N; printf ("%lld", Answer.data[0][0]); return 0;}
洛谷P1962 斐波那契数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。