My Weblog

Blog about programming and math

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;;
		}
	}
Advertisements

January 9, 2011 - Posted by | Programming

4 Comments »

  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

    • In case Fibo(m+2) – Fibo(n+1) become negative which is very much possible.

      Comment by mayankyadav1993 | October 27, 2014 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: