# My Weblog

## SPOJ FIBOSUM

SPOJ Fibonacci Sum is about adding fibonacci number in given range [n,m]. The Wikipedia article says “The sum of the first n Fibonacci numbers is the (n + 2)nd Fibonacci number minus 1″ [second identiy]. Rest is simple.

```#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ll;
ll  MOD=ll( 1000000007);
ll Fibo(int n)
{
ll  fib[2][2]={{1,1},{1,0}},ret[2][2]={{1,0},{0,1}},tmp[2][2]={{0,0},{0,0}};
while(n)
{
if(n&1)
{
memset(tmp,0,sizeof tmp);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)
tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j])%MOD;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) ret[i][j]=tmp[i][j];
}
memset(tmp,0,sizeof tmp);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)
tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j])%MOD;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) fib[i][j]=tmp[i][j];
n/=2;

}
return (ret[0][1])%MOD;
}

int main()
{
int t,m,n;
for(scanf("%d",&t);t>0;t--)
{
scanf("%d%d",&n,&m);
cout<<(Fibo(m+2)-Fibo(n+1)+MOD)%MOD<<endl;;
}
}
```

January 9, 2011 - Posted by | Programming

1. can u please explain the method of this algorithm which u r applying ??
why changing matrix ret() for odd values of n
and dividing n by 2???

Comment by anuarg | January 22, 2011 | Reply

• Hi Anurag, I have already given the wiki link for algorithm. Do you know how to calculate a^n by repeated squaring. For odd value of n , i have taken a tmp matrix for intermediate calculation and coping back it “ret” because i have to return this value as soon as function return. Look at this wiki page http://en.wikipedia.org/wiki/Exponentiation_by_squaring and try to run this fibo function for 3 and you will get idea why we have to copy the tmp value back to ret.

Comment by tiwari_mukesh | January 23, 2011 | Reply

2. why we have added MOD in Fibo(m+2)-Fibo(n+1) ??

Comment by sidharth | December 15, 2012 | Reply