Знову числа Фібоначчі (Розбір)

Теорема. Для чисел Фібоначчі виконується формула:

S (n) = F (0) + F (1) + ... + F (n) = F (n + 2) - 1

S(n) = F(0) + F(1) + ... + F(n) = F(n + 2) - 1

Доказ. Наведемо доказ індукцією.

База індукції. При $n = 0$ n = 0 маємо:

F (0) = F (2) - 1,

F(0) = F(2) - 1,

або $0 = 1 - 1$ 0 = 1 - 1, що вірно.

Крок індукції. Припустимо, що:

S (n) = F (n + 2) - 1

S(n) = F(n + 2) - 1

Тоді:

S (n + 1) = F (0) + F (1) + ... + F (n) + F (n + 1) = (F (n + 2) - 1) + F (n + 1) = F (n + 3) - 1,

S(n + 1) = F(0) + F(1) + ... + F(n) + F(n + 1) = \\ (F(n + 2) - 1) + F(n + 1) = F(n + 3) - 1,

Що і потрібно було довести.

Тоді шукана сума

S = F (a) + F (a + 1) + ... + F (b)

S = F(a) + F(a + 1) + ... + F(b)

може бути знайдена як

S = S (b) - S (a - 1)

S = S(b) - S(a - 1)

Обчислення чисел Фібоначчі через формулу Біне

Розглянемо породжувальну функцію для чисел Фібоначчі ( $F_{0} = 0, F_{1} = 1$ F_0 = 0, F_1 = 1):

G (x) = n = 0 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty (F_{n - 1} + F_{n - 2}) x^{n} = x + n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n} = x + x n = 1 \sum \infty F_{n} x^{n} + x^{2} n = 0 \sum \infty F_{n} x^{n} = x + x G (x) + x^{2} G (x)

G(x) = \sum_{n = 0}^∞ F_n x^n = F_0 + F_1x + \sum_{n = 2}^∞ F_n x^n = \\ F_0 + F_1x + \sum_{n = 2}^∞ (F_{n - 1} + F_{n - 2}) x^n = \\ x + \sum_{n = 2}^∞ F_{n - 1} x^n + \sum_{n = 2}^∞ F_{n - 2} x^n = \\ x + x \sum_{n = 1}^∞ F_n x^n + x^2 \sum_{n = 0}^∞ F_n x^n = \\ x + xG(x) + x^2G(x)

Звідси:

G (x) (1 - x - x^{2}) = x, G (x) = \frac{x}{1 - x - x ^{2}}

G(x) (1 - x - x^2) = x, \\ G(x) = \frac{x}{1 - x - x^2}

Розкладемо породжувальну функцію на прості дроби. Знайдемо корені знаменника:

1 - x - x^{2} = (1 - φ x) (1 - ψ x),

1 - x - x^2 = (1 - φx) (1 - ψx),

де

φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

φ = \frac{1 + \sqrt{5}}{2}, ψ = \frac{1 - \sqrt{5}}{2}

Тепер представимо породжувальну функцію у вигляді:

\frac{x}{1 - x - x ^{2}} = \frac{A}{1 - φ x} + \frac{B}{1 - ψ x}

\frac{x}{1 - x - x^2} = \frac{A}{1 - φx} + \frac{B}{1 - ψx}

Розв'язуючи систему, отримаємо:

A = \frac{1}{5}, B = - \frac{1}{5}

A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}

Враховуючи, що

\frac{1}{1 - r x} = n = 0 \sum \infty r^{n} x^{n},

\frac{1}{1 - rx} = \sum_{n = 0}^∞ r^n x^n,

породжувальну функцію можна переписати у вигляді:

G (x) = \frac{1}{5} (\frac{1}{1 - φ x} + \frac{1}{1 - ψ x}) = \frac{1}{5} n = 0 \sum \infty (φ^{n} - ψ^{n}) x^{n}

G(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - φx} + \frac{1}{1 - ψx} \right) = \frac{1}{\sqrt{5}} \sum_{n = 0}^∞ (φ^n - ψ^n) x^n

Але оскільки

G (x) = n = 0 \sum \infty F_{n} x^{n}

G(x) = \sum_{n = 0}^∞ F_n x^n

то прирівнюючи коефіцієнти при $x^{n}$ x^n, отримаємо:

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5}

F_n = \frac{φ^n - ψ^n}{\sqrt{5}} = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}

Обчислення чисел Фібоначчі через тотожність

Для чисел Фібоначчі відоме наступне тотожність:

F_{n + m} = F_{m} \cdot F_{n + 1} + F_{m - 1} \cdot F_{n}

F_{n + m} = F_m \cdot F_{n+1} + F_{m - 1} \cdot F_n

З нього безпосередньо слідують часткові випадки:

якщо $m = n$ m = n, то $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n
якщо $m = n + 1$ m = n + 1, то $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

Ці формули дозволяють обчислювати числа Фібоначчі методом "поділяй і володарюй", зводячи обчислення $F_{n}$ F_n до значень з приблизно вдвічі меншими індексами.

Окремо обробляються базові випадки:

F_{0} = 0, F_{1} = F_{2} = 1

F_0 = 0, F_1 = F_2 = 1

Завдяки такому підходу глибина рекурсії пропорційна $l o g_{2} n$ log_2n, а часова складність алгоритму становить $O (l o g_{2} n)$ O(log_2n).

Приклад

Обчислимо кілька чисел Фібоначчі за формулою Біне, працюючи в розширеному полі $Z_{p} (5)$ Z_p (\sqrt{5}) за великим модулем $p$ .

F_{2} = \frac{1}{5} (\frac{1 + 5}{2})^{2} - (\frac{1 - 5}{2})^{2} = \frac{( 1 + 5 ) ^{2} - ( 1 - 5 ) ^{2}}{2 ^{2} 5} = \frac{( 6 + 2 5 ) - ( 6 - 2 5 )}{2 ^{2} 5} = \frac{4 5}{4 5} = 1 F_{3} = \frac{1}{5} (\frac{1 + 5}{2})^{3} - (\frac{1 - 5}{2})^{3} = \frac{( 1 + 5 ) ^{3} - ( 1 - 5 ) ^{3}}{2 ^{3} 5} = \frac{( 16 + 8 5 ) - ( 16 - 8 5 )}{2 ^{3} 5} = \frac{16 5}{8 5} = 2 F_{4} = \frac{1}{5} (\frac{1 + 5}{2})^{4} - (\frac{1 - 5}{2})^{4} = \frac{( 6 + 2 5 ) ^{2} - ( 6 - 2 5 ) ^{2}}{2 ^{4} 5} = \frac{( 56 + 24 5 ) - ( 56 - 24 5 )}{2 ^{4} 5} = \frac{48 5}{16 5} = 3

F_2 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 \right) = \frac{(1 + \sqrt{5})^2 - (1 - \sqrt{5})^2}{2^2 \sqrt{5}} = \frac{(6 + 2\sqrt{5}) - (6 - 2\sqrt{5})}{2^2 \sqrt{5}} = \frac{4\sqrt{5}}{4\sqrt{5}} = 1 \\ F_3 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 \right) = \frac{(1 + \sqrt{5})^3 - (1 - \sqrt{5})^3}{2^3 \sqrt{5}} = \frac{(16 + 8\sqrt{5}) - (16 - 8\sqrt{5})}{2^3 \sqrt{5}} = \frac{16\sqrt{5}}{8\sqrt{5}} = 2 \\ F_4 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^4 - \left( \frac{1 - \sqrt{5}}{2} \right)^4 \right) = \frac{(6 + 2\sqrt{5})^2 - (6 - 2\sqrt{5})^2}{2^4 \sqrt{5}} = \frac{(56 + 24\sqrt{5}) - (56 - 24\sqrt{5})}{2^4 \sqrt{5}} = \frac{48\sqrt{5}}{16\sqrt{5}} = 3

Розглянемо на прикладі виконання формул:

якщо $m = n$ m = n, то $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n
якщо $m = n + 1$ m = n + 1, то $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

F_{6} = F_{3} \cdot F_{4} + F_{2} \cdot F_{3} = 2 \cdot 3 + 1 \cdot 2 = 6 + 2 = 8, F_{7} = F_{4}^{2} + F_{3}^{2} = 3^{2} + 2^{2} = 9 + 4 = 13

F_6 = F_3 \cdot F_4 + F_2 \cdot F_3 = 2 \cdot 3 + 1 \cdot 2 = 6 + 2 = 8, \\ F_7 = F_4^2 + F_3^2 = 3^2 + 2^2 = 9 + 4 = 13

Реалізація алгоритму

Оголосимо константу $M O D$ , за модулем якої будуть проводитися обчислення.

#define MOD 1000000007

Оголосимо змінну $f ib$ типу $ma p$ для запам’ятовування вже обчислених чисел Фібоначчі.

map<long long, long long> fib;

Функція f обчислює $n$ -те число Фібоначчі за модулем $M O D$ .

long long f(long long n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n == 2) return 1;

Якщо $n$ -те число Фібоначчі вже було обчислено раніше і збережено в $f ib$ , воно повертається одразу, без повторних обчислень.

  if (fib[n]) return fib[n];

Далі використовуємо розкладання числа $n$ на:

$n = 2 k + 1$ n = 2k + 1 — непарний випадок: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ F_n = F_k^2 + F_{k + 1}^2.
$n = 2 k$ n = 2k — парний випадок: $F_{n} = F_{k} \cdot F_{k + 1} + F_{k - 1} \cdot F_{k}$ F_n = F_k \cdot F_{k + 1} + F_{k - 1} \cdot F_k.

  long long k = n / 2;

Зберігаємо і повертаємо результат.

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

Основна частина програми. Для кожного тесту читаємо вхідні дані і виводимо відповідь.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (f(b + 2) - f(a + 1) + MOD) % MOD);

Реалізація алгоритму – формула Біне

Оголосимо константу $M O D$ , за модулем якої будуть проводитися обчислення.

#define MOD 1000000007

Оголосимо структуру $N u m$ для зберігання числа виду $x + y 5$ 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_) {}
};

Реалізуємо множення в полі $Z_{p} (5)$ Z_p (\sqrt{5}). Функція mult повертає добуток чисел $a$ та $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;
}

C++

Функція pow реалізує піднесення в степінь $ba s e^{n}$ base^n, де $ba se$ — число в полі $Z_{p} (5)$ 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;
}

C++

Функція modpow обчислює значення $a^{k} m o d p$ 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;
}

C++

Функція fib обчислює $n$ -те число Фібоначчі.

long long fib(long long n)
{

Ініціалізуємо константи $φ = 1 + 5$ φ = 1 + \sqrt{5} та $ψ = 1 - 5$ ψ = 1 - \sqrt{5}.

  Num phi(1, 1);
  Num psi(1, MOD - 1);

Обчислюємо степені $A = φ^{n}$ A = φ^n та $B = ψ^{n}$ B = ψ^n.

  Num A = pow(phi, n);
  Num B = pow(psi, n);

Оскільки

F_{n} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5} = \frac{( A _{x} + A _{y} 5 ) - ( B _{x} + B _{y} 5 )}{2 ^{n} 5},

F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}} = \frac{(A_x + A_y \sqrt{5}) - (B_x + B_y \sqrt{5})}{2^n \sqrt{5}},

обчислюємо окремо чисельник та знаменник.

Відзначимо, що $A_{x} = B_{x}$ A_x = B_x (тому $A_{x} - B_{x} = 0$ A_x - B_x = 0), а коефіцієнт при $5$ \sqrt{5} в чисельнику дорівнює $A_{y} - B_{y}$ A_y - B_y.

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

Обчислюємо $2^{n}$ 2^n у знаменнику.

  long long denom = pow(2, n);

Чисельник та знаменник містять множник $5$ \sqrt{5}. Скоротимо дріб на нього. Тепер залишається обчислити результат, який дорівнює

(A_{y} - B_{y}) \cdot (2^{n})^{- 1} = n u m er a t or \cdot d e n o m^{- 1}

(A_y - B_y) \cdot (2^n)^{-1} = numerator \cdot denom^{-1}

  long long denom_inv = pow(denom, MOD - 2);
  return numerator * denom_inv % MOD;
}

Основна частина програми. Для кожного тесту читаємо вхідні дані і виводимо відповідь.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (fib(b + 2) - fib(a + 1) + MOD) % MOD);