Algorithm
Problem link- https://www.spoj.com/problems/FIBOSUM/
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
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class matrix:
a = []
def __init__(self, default=None):
if default is not None:
self.a = default
else:
self.a = [[0, 0], [0, 0]]
def __mul__(self, other):
s = matrix()
for i in range(2):
for j in range(2):
for k in range(2):
s.a[i][j] += self.a[i][k] * other.a[k][j]
for i in range(2):
for j in range(2):
s.a[i][j] %= 1000000007
return s
def __pow__(self, power, modulo=None):
if power == 1:
return matrix([[1, 1], [1, 0]])
if power % 2 == 1:
return self * (self.__pow__(power - 1))
half = self.__pow__(power // 2)
return half * half
def get(n, modulo):
m = matrix([[1, 1], [1, 0]]) ** (n + 2)
return (m.a[0][1] + modulo - 1) % modulo
modulo = 1000000007
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
print((get(M, modulo) - get(N - 1, modulo) + modulo) % modulo)Input
3
0 3
3 5
10 19
0 3
3 5
10 19
Output
4
10
10857
10
10857
Demonstration
SPOJ Solution-Fibonacci Sum-Solution in C, C++, Java, Python