HI @abhishek_trigunait bhaiya and @Abhishek_ranjan bhaiya i am trying to solve fibonacci using fast exponentiation but two of the test cases are failing . could you please let just give me the hint what i am missing .
https://ide.codingblocks.com/#/s/14175
and as in question series is starting from 1 so i am doing System.out.println(FastFib(sc.nextInt() -2));
could you please suggest me what is the better way of achieving the same .
where is your power() function? Shouldn’t you be doing power(F, n/2) somewhere
HI @abhishek_trigunait bhaiya - that part i am handling through binary exponentiation .
in-spite of dividing power on the basis of odd and even i am multiplying matrix on the basis of its set bits .
for ex - f(10) = 1 1 ^ 9 f(0)
1 0 f(1)
and later on i am multiplying matrix with itself on the basis of set bits in 9 .
is this approach fine ?
Using this approach i am able to get the fibonacci number for all the numbers in my local ide but its failing here .
Please suggest me the correct approach .
And for FIBOSUM problem also i am getting tle , wrong answer and run-time error
https://ide.codingblocks.com/#/s/14212
what i am missing here ?
Your code runs in O(n*(b-a)), but to get accepted, it shouldn’t take more than O(nlogn). Instead of looping from 2 to b-a, use the property f(0)+f(1)+f(2)+...+f(n) = f(n+2)-1. And just take N and M as input and print (fib(M + 2) - 1) - (fib(N + 2) - 1) - fib (N) i.e. fib (M + 2) - fib (N + 1) as output, where fib(X) returns Xth fibonacci number.
HI @abhishek_trigunait bhaiya - i am not able to understand completely but i will share my understanding and doubt .
what i understood from above explanation :-
when N and M are given as an input in that case linear recurrence we can have as below
f(N) + f(N+1)+f(N+2)+ -------+f(M) = f(M+2) - f(N+1)
if that is the case , how i can get the transformation matrix for this linear recurrence . I am not getting this .
If my above understanding is correct than please help me with the transformation matrix for it or else please correct me ?
And as well in such problems how we can find out linear recurrence for any of the given problem ?
Second Doubt (Fast Fibonacci https://hack.codingblocks.com/contests/c/473/280):
For this problem i am getting wrong answer for two of the test cases could you please let me know where i am missing .
https://ide.codingblocks.com/#/s/14175
I am trying to solve it using matrix and binary exponentiation .
That is not really a linear recurrence, just a handy theorem.
And regarding that transformation matrix thing, you just make a function ( say fib(int n)) which accepts a number say n and returns the nth fibonacci number. Now for every case, you just need to print out fib(M+2) - fib(N+1).
In your code LINE 33, where you’re doing result[i][j] += transformationMatrix1[i][k] * transformationMatrix2[k][j], result[i][j] may store an overflowing value, so you need to put MODULUS here too : result[i][j] = (result[i][j] + transformationMatrix1[i][k] * transformationMatrix2[k][j])%1000000007 and you’re done.
okay so in this problem i have to calculate fib(M+2) - fib(N+1) for any of the given N and M right ?
That’s correct…
Thanks a lot @abhishek_trigunait bhaiya . Could you please let me know from where i can learn all these theorem.
Don’t mention it, just hit the 
and I’ll know 
There’s no specific book or webpage, you’ll learn things as you go on solving problems and searching the web as and when the need arises. BTW, GeeksForGeeks contains most of the useful stuffs.
I did the modification as per the theorem but still it’s giving wrong answer am i missing any edge case ?
It is quite possible that result may get a negative value (due to wrapping up of the larger number and the smaller number being less than 1000000007), so before printing result, you need to do if( result < 0 ) result += 1000000007
Sorry i didn’t get this scenario . Could you please tell me some example for it .
Lets say you have x = 2 and y = 5 with constraints 0 <= x <= y <= 1000 ( similar to those constraints ), now you need to print result = f(y) - f(x) where f() is a monotonically increasing function. Now, f(y) is always greater than or equal to f(x), but you decide to put a modulus in the return value of the function. Lets say mod = 13. Now, say f(2) returns 11 and f(5) returns 16. But since you’re returning the value %13, the variable result which stores f(5) - f(2) now, gets a value of 16%13 - 11%13 = -8. So in this case you need to do result += 13 i.e. result will have 5 which was supposed to be the correct answer(16-11).
really helpfull 