题目描述
大家都知道，斐波那契数列是满足如下性质的一个数列：
Fn={1 (n≤2)Fn−1+Fn−2 (n≥3)
请你求出 Fnmod109+7 的值。
输入格式
一行一个正整数 n。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1复制
5
输出 #1复制
5
输入 #2复制
10
输出 #2复制
55
说明/提示
【数据范围】
对于 60% 的数据，1≤n≤92；
对于 100% 的数据，1≤n<263。
代码实现：
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 long long n; long long m[2][2]={{0,1},{1,1}},t[2][2]; long long res[2]={0,1},tmp[2]; void matmul_vec() { memset(tmp,0,sizeof(tmp)); for(int i=0;i<2;i++) for(int k=0;k<2;k++) tmp[i]=(tmp[i]+res[k]*m[k][i])%mod; memcpy(res,tmp,sizeof(tmp)); return; } void matmul_mat() { memset(t,0,sizeof(t)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) t[i][j]=(t[i][j]+m[i][k]*m[k][j])%mod; memcpy(m,t,sizeof(t)); return; } int main() { scanf("%lld",&n); while(n) { if(n%2) matmul_vec(); matmul_mat(); n/=2; } printf("%d\n",res[0]%mod); return 0; }
)
