Thursday, 22 January 2015

fibosum (spoj) fibonacci

question link http://www.spoj.com/problems/FIBOSUM/

geeksfor geeks link http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

finding nth fibo number in O(log n)

imp concept for Fibonacci sum
fibosum(x)= fibonum(x+2) -1 ;

#include<stdio.h>
typedef unsigned long long ll ;
using namespace std;
ll f[2][2]={{1,1},{1,0}};
int te[2][2]={{1,1},{1,0}};
ll mo=1000000007;

int mul(int n)
{
        ll t[2][2]={0,0,0,0};
    if(n==1)
    {
        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]+f[i][k]*te[k][j])%mo;
            }
        }
         for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                f[i][j]=t[i][j];
            }
        }
    }
    else
    {
        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]+f[i][k]*f[k][j])%mo;
            }
        }
         for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                f[i][j]=t[i][j];
            }
        }
    }

}

int power(ll n)
{
    if(n<=1)
        return 0;
       // n<<2;
    power(n/2);
    mul(2);
    if(n&1)
        mul(1);

}

int fibo(ll a)
{
    if(a==0)
        return 0;
    power(a-1);
}

int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll a,b,q,w,e;
        //scanf("%llu %llu",&a,&b);
        scanf("%llu %llu",&a,&b);
        fibo(a+1);
        q=f[0][0];
       // printf("%llu\n",f[0][0]);
        //printf("%d %d %d %d",te[0][0],te[1][0],te[0][1],te[1][1]);
        f[0][0]=1;
        f[0][1]=1;
        f[1][0]=1;
        f[1][1]=0;
        fibo(b+2);
        w=f[0][0];
       // printf("%llu\n",w);
        e=(w-q+mo)%mo;
        printf("%llu\n",e);
          f[0][0]=1;
        f[0][1]=1;
        f[1][0]=1;
        f[1][1]=0;



    }
}