# coreBugZJ

## FIB Query, 1007, 2011 Multi-University Training Contest 10

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.

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

posted on 2011-08-11 17:21 coreBugZJ 阅读(267) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithmMathematics