非水斐波那契数列
题目描述
斐波那契数列:1,1,2,3,5,8,13……请你编程计算出第n项%1000000007的值(n<=10^15).
输入
一个整数n(n<=10^15)
输出
数列第n项的值
样例输入
4
样例输出
3
提示
温馨提示:10^15>2^31-1
代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 using namespace std; 5 6 const int Maxn = 1000000007; 7 8 struct matrix { 9 long long m[2][2]; 10 }; 11 12 matrix multi(matrix a, matrix b) { 13 long long sums = 0; 14 matrix c; 15 memset(c.m, 0, sizeof(c.m)); 16 for (int i = 0; i <= 1; i++) { 17 for (int j = 0; j <= 1; j++) { 18 sums = 0; 19 for (int k = 0; k <= 1; k++) { 20 sums = (sums + a.m[i][k] * b.m[k][j]) % Maxn; 21 } 22 c.m[i][j] = sums % Maxn; 23 } 24 } 25 return c; 26 } 27 28 matrix matmod(matrix a, long long k) { 29 matrix res; 30 memset(res.m, 0, sizeof(res.m)); 31 for (int i = 0; i <= 1; i++) { 32 res.m[i][i] = 1; 33 } 34 while(k) { 35 if (k & 1) { 36 res = multi(res, a); 37 } 38 k = (k >> 1); 39 a = multi(a, a); 40 } 41 return res; 42 } 43 44 int main() { 45 long long n; 46 scanf("%lld", &n); 47 if (n < 3) { 48 printf("1"); 49 } 50 else { 51 matrix a, b; 52 memset(a.m, 0, sizeof(a.m)); 53 memset(b.m, 0, sizeof(b.m)); 54 for (int i = 0; i <= 1; i++) { 55 a.m[i][1] = 1; 56 } 57 for (int i = 0; i <= 1; i++) { 58 b.m[i][0] = 1; 59 } 60 a.m[1][0] = 1; 61 a = matmod(a, n - 2); 62 a = multi(a, b); 63 printf("%d", a.m[1][0]); 64 } 65 return 0; 66 }