FIB Query
TimeLimit: 2 Second MemoryLimit: 64 Megabyte
Totalsubmit: 733 Accepted: 87
Description
We all know the definition of Fibonacci series: fib[i]=fib[i-1]+fib[i-2],fib[1]=1,fib[2]=1.And we define another series P associated with the Fibonacci series: P[i]=fib[4*i-1].Now we will give several queries about P:give two integers L,R, and calculate ∑P[i](L <= i <= R).
Input
There is only one test case.
The first line contains single integer Q – the number of queries. (Q<=10^4)
Each line next will contain two integer L, R. (1<=L<=R<=10^12)
Output
For each query output one line.
Due to the final answer would be so large, please output the answer mod 1000000007.
Sample Input
2
1 300
2 400
Sample Output
838985007
352105429
Source
[p][/p]
p[1] + p[2] + ... + p[n] = f[1]^2 + f[2]^2 + ... + f[2*n-1]^2 + f[2*n]^2 = f[2*n] * f[2*n+1]
1 #include <iostream>
2 #include <cstring>
3
4 using namespace std;
5
6 #define MOD 1000000007
7
8 typedef long long I64;
9
10 void getF( I64 n, I64 *fn, I64 *fnp1 ) {
11 I64 m[ 2 ][ 2 ], t[ 2 ][ 2 ], p[ 2 ][ 2 ];
12 int i, j, k;
13
14 m[ 0 ][ 0 ] = 1;
15 m[ 0 ][ 1 ] = 0;
16 m[ 1 ][ 0 ] = 0;
17 m[ 1 ][ 1 ] = 1;
18
19 p[ 0 ][ 0 ] = 1;
20 p[ 0 ][ 1 ] = 1;
21 p[ 1 ][ 0 ] = 1;
22 p[ 1 ][ 1 ] = 0;
23
24 while ( n != 0 ) {
25 if ( n & 1 ) {
26 for ( i = 0; i < 2; ++i ) {
27 for ( j = 0; j < 2; ++j ) {
28 t[ i ][ j ] = 0;
29 for ( k = 0; k < 2; ++k ) {
30 t[i][j] = (t[i][j]+m[i][k]*p[k][j]) % MOD;
31 }
32 }
33 }
34 for ( i = 0; i < 2; ++i ) {
35 for ( j = 0; j < 2; ++j ) {
36 m[ i ][ j ] = t[ i ][ j ];
37 }
38 }
39 }
40
41 n >>= 1;
42 for ( i = 0; i < 2; ++i ) {
43 for ( j = 0; j < 2; ++j ) {
44 t[ i ][ j ] = 0;
45 for ( k = 0; k < 2; ++k ) {
46 t[i][j] = (t[i][j]+p[i][k]*p[k][j]) % MOD;
47 }
48 }
49 }
50 for ( i = 0; i < 2; ++i ) {
51 for ( j = 0; j < 2; ++j ) {
52 p[ i ][ j ] = t[ i ][ j ];
53 }
54 }
55 }
56 *fnp1 = m[ 0 ][ 0 ];
57 *fn = m[ 1 ][ 0 ];
58 }
59
60 void getP( I64 n, I64 *pn ) {
61 I64 fn, fnp1;
62 n = n + n;
63 getF( n, &fn, &fnp1 );
64 *pn = ( fn * fnp1 ) % MOD;
65 }
66
67 int main() {
68 int q;
69 I64 le, ri, pl, pr;
70 cin >> q;
71 while ( q-- > 0 ) {
72 cin >> le >> ri;
73 getP( le-1, &pl );
74 getP( ri, &pr );
75 cout << ( ( pr + MOD - pl ) % MOD ) << "\n";
76 }
77 return 0;
78 }
79