| 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
|
||||||||||||||
|
2024-10-14 15:39:05
Good Problem for matrix exponentiation understanding |
||||||||||||||
|
2024-07-30 14:56:06
Use the property of that The sum of n terms of Fibonacci Sequence is given by Σi=0n Fi = Fn+2 - F2 (or) Fn+2 - 1 as suggested by @prash8830 also take care of negative numbers in modulo operations. |
||||||||||||||
|
2024-03-10 23:58:06
MY FIRST AC IN ONE!!!!!! LET'S GOOOOOOO! it's really annoying reading this kind of comments but it doesn't matter if you ac in one or in two or in seven. Just keep coding ;) |
||||||||||||||
|
2023-03-17 20:18:58
use long long and don't use unsigned long long like me. make sure you modulus every intermediate matrix sum. write a helper function for modulus to check if negative and add 1000000007 if so. fib range sum is fib(M+2) - fib(N+1) here are some other cases: 1000000 100000000 -> 319410664 10 1000000000 -> 999999926 Last edit: 2023-03-17 20:20:22 |
||||||||||||||
|
2022-07-14 08:51:03
Fibonacci Sequence Sum Property : The sum of n terms of Fibonacci Sequence is given by Σi=0n Fi = Fn+2 - F2 (or) Fn+2 - 1, where Fn is the nth Fibonacci number. (Note: the first term starts from F0) For example, the sum of first 10 terms of sequence = 12th term - 1 = 89 - 1 = 88. It can be mathematically written as Σi=09 Fi = F11 - 1 = 89 - 1 = 88. |
||||||||||||||
|
2022-01-27 07:12:36
Mod can decrease the value of large interger values |
||||||||||||||
|
2021-12-01 10:06:58
everyone is telling matrix exponentiation but no one is actually explaining the idea behind the summation stuff. It's not like everyone understands everything, but only some basics like the Fibonacci series or calculating large Fibonacci numbers. |
||||||||||||||
|
2021-05-06 06:49:36
I did matrix exponentiation upto n and then I multiply by matrix power of 2 each time until i reach m, I'm getting the correct answer but time limit is exceeded. Anyone have ideas for removing the stepping by 2 factor? I guess that should be cause. thanks |
||||||||||||||
|
2021-02-11 12:48:21
!!IMPORTANT!! use (a%mod -b%mod +mod)%mod) instead of (a-b)%mod |
||||||||||||||
|
2020-12-02 15:46:22
Nice problem for matrix exponentiation |
||||||||||||||
RSS