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;; } }
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 |
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 |
why we have added MOD in Fibo(m+2)-Fibo(n+1) ??
Comment by sidharth | December 15, 2012 |
In case Fibo(m+2) – Fibo(n+1) become negative which is very much possible.
Comment by mayankyadav1993 | October 27, 2014 |