题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列：
• 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 2 struct 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; }