Fibonacci problem again (Editorial)

Theorem. For the Fibonacci numbers, the following formula holds:

Proof. We prove the statement by induction.

• Base case. For n = 0 we have:

That is, 0 = 1 - 1, which is true.

• Inductive step. Assume that:

Then:

which completes the proof

Then the desired sum

can be computed as

Computing Fibonacci numbers using Binet's formula

Consider the generating function for the Fibonacci numbers (F_0 = 0, F_1 = 1):

From this it follows that:

Let us decompose the generating function into partial fractions. First, find the roots of the denominator:

where

Now represent the generating function as:

Solving the system, we obtain:

Taking into account that

the generating function can be rewritten as:

But since

equating the coefficients of x^n gives:

Computing Fibonacci Numbers Using an Identity

For the Fibonacci numbers, the following identity is known:

From it, the following special cases follow directly:

• if m = n, then F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n

• if m = n + 1, then F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

These formulas make it possible to compute Fibonacci numbers using a divide-and-conquer approach, reducing the computation of F_n to values with indices approximately half as large.

The base cases are handled separately:

With this approach, the recursion depth is proportional to log_2n, and the time complexity of the algorithm is O(log_2n).

Example

Let us compute some Fibonacci numbers using Binet’s formula, working in the extended field Z_p (\sqrt{5}) with a large modulus $p$.

Let us illustrate the application of the formulas with an example:

• if m = n, then F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n

• if m = n + 1, then F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

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: F_n = F_k^2 + F_{k + 1}^2.

• n = 2k — even case: F_n = F_k \cdot F_{k + 1} + F_{k - 1} \cdot F_k.

  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 x + y \sqrt{5}.

struct Num
{
  long long x, y; // x + y*sqrt(c)
  Num(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};

Implement multiplication in the field Z_p (\sqrt{5}). 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 base^n, where $base$ is a number in the field Z_p (\sqrt{5}).

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 a^k~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 + \sqrt{5} and ψ = 1 - \sqrt{5}.

  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 A_x = B_x (so A_x - B_x = 0), and the coefficient of \sqrt{5} in the numerator is A_y - B_y.

  long long numerator = (A.y - B.y + MOD) % MOD;

Compute 2^n in the denominator.

  long long denom = pow(2, n);

Both the numerator and the denominator contain a factor of \sqrt{5}. Cancel this factor, leaving the result to be computed as:

  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);