SPOJ-FIBSUM

hello friends today i will teach how to find fibonacci in O(logn) time...

here the basis is find the fibonacci for n+1th element
and find the fibonacci for m+2th element.
and subtract the two to get the result..

possible bug
1)
use long long to store the values and then apply mod on it... because
suppose..
int x=4294967296(maximum value int can store!!!!)
int y=4294967296(maximum value int can store!!!!)
x=(x+y)%M
this will also show some value but THAT WILL BE GARBAGE .... because on adding u exceeded the limit then again tried to come back in the limit by doing mod...

2)
on subtracting it may happen the value becomes negative and u are applying mod on that so to prevent do this

long long x=(a-b+M)%M
this removes that error...

thats all read the program and comment if u cannot understand..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

#include<bits/stdc++.h> typedef long long ll; #define M 1000000007 void mult(ll f[][2],ll m[][2]) { ll w=(f[0][0]*m[0][0]+f[0][1]*m[1][0])%M; ll x=(f[0][0]*m[0][1]+f[0][1]*m[1][1])%M; ll y=(f[1][0]*m[0][0]+f[1][1]*m[1][0])%M; ll z=(f[1][0]*m[0][1]+f[1][1]*m[1][1])%M; f[0][0]=w; f[0][1]=x; f[1][0]=y; f[1][1]=z; } void power(ll f[][2],ll n) { ll m[2][2]={{1,1},{1,0}}; if(n==0 || n==1) return; power(f,n/2); mult(f,f); if(n%2) mult(f,m); } void init(ll f[][2]) { f[0][0]=1; f[0][1]=1; f[1][0]=1; f[1][1]=0; } int main() { int t,n,m; scanf("%d",&t); while(t--) { ll f[2][2],sum=0; init(f); scanf("%d %d",&n,&m); power(f,n); ll a=f[0][0]; init(f); power(f,m+1); a=(f[0][0]-a+M)%M; printf("%lld\n",a); } return 0; }