1250. Fibonacci problem again
As is well known, the
Fibonacci numbers are defined as follows:
Given two integers a
and b, compute the sum
S = F(a) + F(a
+ 1) + … + F(b)
Input. Each line represents a
separate test case and contains two integers a and b (0 ≤ a
≤ b ≤ 109).
Output. For each test case, print
on a separate line the value of S modulo 109 + 7.
|
Sample
input |
Sample
output |
|
1 1 3 5 10 1000 |
1 10 625271457 |
SOLUTION
Fibonacci
numbers
Algorithm analysis
Theorem. For the Fibonacci numbers,
the following formula holds
S(n) = F(0) + F(1)
+ … + F(n) = F(n + 2) – 1
Proof. We prove the statement by
induction.
·
Base case. For n = 0 we have:
F(0) = F(2) – 1,
That is, 0 = 1 – 1, which is true.
·
Inductive step. Assume that:
S(n) = F(n +
2) – 1
Then:
S(n + 1) = F(0) + F(1) + … + F(n) + F(n + 1) =
(F(n + 2) – 1) + F(n + 1) = F(n + 3) – 1,
which completes the proof.
Then the desired sum
S = F(a) + F(a
+ 1) + … + F(b)
can be computed as
S = S(b) – S(a –
1)
Computing Fibonacci
numbers using Binet’s formula
Consider the generating
function for the Fibonacci numbers (F0 = 0, F1
= 1):
G(x) = 
= F0 + F1x
+ 
=
F0 + F1x
+ 
=
x + 
+ 
=
x + 
+ 
=
x + xG(x) + x2G(x)
From this it follows that:
G(x) (1 – x
– x2) = x,
G(x) = 
Let us decompose the
generating function into partial fractions. First, find the roots of the
denominator:
1 – x – x2
=
(1 – φx) (1 – ψx),
where
φ = 
, ψ = 
Now represent the
generating function as:
= 
+ 
Solving the system, we
obtain:
A = 
, B = 
Taking into account that
= 
,
the generating function
can be rewritten as:
G(x) = 
= 
But since
G(x) =
equating the coefficients
of xn gives:
= 
= 
Computing Fibonacci
Numbers Using an Identity
For the Fibonacci numbers,
the following identity is known:
Fn+m
= Fm ∙ Fn+1 + Fm-1
∙ Fn
From it, the following
special cases follow directly:
·
if m = n, then F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn
·
if m = n + 1, then F2n+1 = Fn+1
∙ Fn+1 + Fn ∙ Fn
These formulas make it
possible to compute Fibonacci numbers using a divide-and-conquer
approach, reducing the computation of Fn to values with indices approximately
half as large.
The base cases are handled
separately:
F0 =
0, F1 =
F2 = 1
With this approach, the
recursion depth is proportional to log2n, and the time complexity of the
algorithm is O(log2n).
Example
Let us compute some
Fibonacci numbers using Binet’s formula, working in the extended field 
with a large modulus p.
= 
= 
= 
= 
= 1
= 
= 
= 
= 
= 2
= 
= 
= 
= 
= 3
Let us
illustrate the application of the formulas with an example:
·
if m = n, then F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn
·
if m = n + 1, then F2n+1 = Fn+1
∙ Fn+1 + Fn ∙ Fn
F6 = F3 ∙ F4 + F2 ∙ F3 = 2 * 3 + 1 * 2 = 6 + 2 =
8,
F7 = 
+ 
= 32 + 22 = 9 + 4 = 13
Algorithm implementation
Declare the constant MOD, which will be used as the modulus for all
computations.
#define MOD 1000000007
Declare a variable fib of type map to store (memoize)
already computed Fibonacci numbers.
map<long long, long long>
fib;
The function f computes the n-th Fibonacci
number modulo MOD.
long long f(long long n)
{
if (n ==
0) return 0;
if (n ==
1) return 1;
if (n ==
2) return 1;
If the n-th Fibonacci number has already been computed and stored in fib, it is returned
immediately without recomputation.
if (fib[n]) return fib[n];
Next, we decompose the number n as
follows:
·
n = 2k + 1 – odd case: 
.
·
n = 2k – even case: 
.
long long k = n / 2;
Store the result and
return it.
if (n % 2
== 1) // n = 2*k + 1
return fib[n] =
(f(k) * f(k) + f(k + 1) * f(k + 1)) % MOD;
else // n
= 2*k
return fib[n] =
(f(k) * f(k + 1) + f(k - 1) * f(k)) % MOD;
}
The main part of the program. For each test case, read the input data and print the answer.
while (scanf("%lld %lld",
&a, &b) == 2)
printf("%lld\n",
(f(b + 2) - f(a + 1) + MOD) % MOD);
Algorithm implementation – Binet’s formula
Declare the constant MOD, which will be used as the modulus for all
computations.
#define MOD 1000000007
Declare the structure Num
to store a number of the form 
.
struct Num
{
long long x, y; // x + y*sqrt(5)
Num(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};
Implement multiplication in the field . The function mult
returns the product of the numbers a and b.
Num mult(Num& a, Num& b)
{
Num res;
res.x = (a.x * b.x + 5 * a.y % MOD * b.y) % MOD;
res.y =
(a.x * b.y + a.y * b.x) % MOD;
return res;
}
The function pow performs exponentiation of basen,
where base is a number in the field .
Num pow(Num base, long long n)
{
Num res = { 1, 0 };
while (n > 0)
{
if (n & 1)
res = mult(res, base);
base = mult(base, base);
n >>= 1;
}
return res;
}
The function modpow
computes the value of ak mod p.
long long pow(long long x, long long n)
{
long long res = 1;
x %= MOD;
while (n > 0)
{
if (n & 1) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
The function fib computes the n-th Fibonacci number.
long long fib(long long n)
{
Initialize the constants φ = 1 + 
and ψ = 1 – .
Num phi(1, 1);
Num psi(1, MOD - 1);
Compute the powers A = φn and B = ψn.
Num A = pow(phi, n);
Num B = pow(psi, n);
Since
= = = 
,
compute the numerator and denominator separately.
Note that 
= 
(so – = 0), and the
coefficient of in the numerator is 
– 
.
long long numerator = (A.y - B.y
+ MOD) % MOD;
Compute 2n in the
denominator.
long long denom = pow(2, n);
Both the numerator and the denominator contain a factor of . Cancel this
factor, leaving the result to be computed as:
= numerator * denom-1
long long denom_inv = pow(denom,
MOD - 2);
return numerator * denom_inv
% MOD;
}
The main part of the program. For each test case, read the input data and print the answer.
while (scanf("%lld %lld", &a, &b) == 2)
printf("%lld\n", (fib(b + 2) -
fib(a + 1) + MOD) % MOD);