FIBOSUM - Fibonacci Sum
The fibonacci sequence is defined by the following relation:
- F(0) = 0
- F(1) = 1
- F(N) = F(N - 1) + F(N - 2), N >= 2
Your task is very simple. Given two non-negative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
The first line contains an integer T (the number of test cases). Then, T lines follow. Each test case consists of a single line with two non-negative integers N and M.
For each test case you have to output a single line containing the answer for the task.
Input: 3 0 3 3 5 10 19 Output: 4 10 10857
- T <= 1000
- 0 <= N <= M <= 109
Finally AC after 9 WA,3TLE
use (a%mod -b%mod +mod)%mod) instead of (a-b)%mod
The case of negative modulos is interesting....
normal iteration won't work, will obviously give TLE
Take Care of Data Type...! Got 2 WA for using int and long int.
sum(m) - sum(n-1) can be negative because sum(m) & sum(n-1) are not real answers but instead (real answer)%MOD and there is a possibility that sum(n-1) will be greater than sum(m). So, do ((sum(m)-sum(n-1)%MOD)%MOD which will handle both +ve and -ve numbers. Learnt Matrix Exponentiation because of this !!!
At last...was fed up with rte.
Negative cases are possible so beware of that.
can be done using partial sum
This is too much cheap!! :/ "N<=M" has been said in constrain. But further they have set input against the constrain in order to make the problem a bit harder. Negative answers never be possible if N<=M. But using this "cout<<(fibonacci(b+2)-fibonacci(a+1)+mod)%mod<<endl; " instead of "cout<<fibonacci(b+2)-fibonacci(a+1)<<endl; " got AC.