2015
04-14

# FIB Query

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).

There is only one test case.
The first line contains single integer Q �C the number of queries. (Q<=10^4)
Each line next will contain two integer L, R. (1<=L<=R<=10^12)

There is only one test case.
The first line contains single integer Q �C the number of queries. (Q<=10^4)
Each line next will contain two integer L, R. (1<=L<=R<=10^12)

2
1 300
2 400

838985007
352105429

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int mod=1000000007;
const int gg=400000003;
int unit[ 3 ][ 3 ]={{2,0,-1},{1,0,0},{0,1,0}};
int ma[ 3 ][ 3 ][ 3 ];
void init( int to ){
for( int i=0;i<3;i++ )
for( int j=0;j<3;j++ )
ma[ to ][ i ][ j ]=unit[ i ][ j ];
}
void macpy( int to,int from ){
for( int i=0;i<3;i++ )
for( int j=0;j<3;j++ )
ma[ to ][ i ][ j ]=ma[ from ][ i ][ j ];
}
void cal( int a,int b,int c ){
for( int i=0;i<3;i++ )
for( int j=0;j<3;j++ ){
ma[ c ][ i ][ j ]=0;
for( int k=0;k<3;k++ )
ma[ c ][ i ][ j ]=( (long long)ma[ a ][ i ][ k ]*ma[ b ][ k ][ j ]+ma[ c ][ i ][ j ] )%mod;
}
}
void gao( long long len ){
if( len==1 ){
init( 2 );
return;
}
gao( len/2 );
if( len%2 ){
init( 1 );
cal( 2,1,0 );
cal( 2,0,1 );
macpy( 2,1 );
}
else{
cal( 2,2,1 );
macpy( 2,1 );
}

}
long long get( void ){
return ( ( long long )ma[ 2 ][ 0 ][ 0 ]*4+(long long)ma[ 2 ][ 0 ][ 1 ]*2+(long long)ma[ 2 ][ 0 ][ 2 ]+(long long)ma[ 2 ][ 2 ][ 0 ]*4+(long long)ma[ 2 ][ 2 ][ 1 ]*2+(long long)ma[ 2 ][ 2 ][ 2 ]+1)%mod;
}
int main( void ){

int q;
scanf( "%d",&q );
for( ;q;q-- ){
long long l,r,cl=0,cr;
scanf( "%I64d%I64d",&l,&r );
if( --l ){
gao( 4*l-3 );
cl=get( );
}
gao( 4*r-3 );
cr=get( );
printf( "%d\n",( int )( ( ( ( ( cr-cl )%mod )*gg)%mod+mod )%mod ) );
}
}

1. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

2. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

3. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

4. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

5. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

6. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

7. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

8. 抗争是普通人做不到的,所以是英雄,应当被那些普通人敬仰赞美,沉默是普通人,庸众羊群,可以理解和宽容,但也不必炫耀自己,不值得敬仰,

9. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。