Submit | All submissions | Best solutions | Back to list |
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.
Input
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.
Output
For each test case you have to output a single line containing the answer for the task.
Example
Input: 3 0 3 3 5 10 19 Output: 4 10 10857
Constraints
- T ≤ 1000
- 0 ≤ N ≤ M ≤ 109
Added by: | David Gómez |
Date: | 2010-12-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | My Own |
hide comments
|
||||||||||||||
2017-12-24 21:40:59
Learnt matrix expo: but not tried with f(n+2)-1 :) |
||||||||||||||
2017-12-14 21:46:06
Matrix exponentiation and f(1)+f(2)+f(3)+... + f(n) = f(n+2)-1 did this :D !! 82nd AC |
||||||||||||||
2017-10-08 19:06:09
Matrix Expo :) |
||||||||||||||
2017-06-23 10:31:35
learn something new !! Matrix exponentiation !! care about mod !! |
||||||||||||||
2017-06-14 22:46:36
use long long !! Cost me 3WA's |
||||||||||||||
2017-06-11 14:07:35
Why will it ever be negative? @sagnik_66 Last edit: 2017-06-11 14:07:57 |
||||||||||||||
2017-06-09 18:23:45
Take care about the negative answers. Just add 1000000007. Matrix Exponentiation gives answer in 0.0 secs |
||||||||||||||
2017-05-30 13:19:40
@vineetpratik can you show me your dijkshra code?? how did you memorized the fibonacci no. since constrains is 10e9! and we cant save this much in memory |
||||||||||||||
2017-05-05 11:34:57
Jbardast Problem |
||||||||||||||
2017-04-05 16:02:14
2 TLE 2 WA and finally AC:) |