1250. Опять числа Фибоначчи
Как известно, числа
Фибоначчи определяются следующим образом:
Даны два целых
числа a и b. Вычислите
сумму:
S = F(a) + F(a
+ 1) + … + F(b)
Вход. Каждая строка является отдельным тестом и содержит два целых числа
a и b (0 ≤ a ≤ b ≤ 109).
Выход. Для каждого теста выведите в отдельной строке значение S по модулю 109 + 7.
|
Пример
входа |
Пример
выхода |
|
1 1 3 5 10 1000 |
1 10 625271457 |
РЕШЕНИЕ
числа Фибоначчи
Анализ алгоритма
Теорема. Для чисел
Фибоначчи выполняется формула:
S(n) = F(0) + F(1)
+ … + F(n) = F(n + 2) – 1
Доказательство. Приведем
доказательство по индукции.
·
База индукции. При n = 0 имеем:
F(0) = F(2) – 1,
или 0 = 1 – 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 = F(a) + F(a
+ 1) + … + F(b)
может быть
найдена как
S = S(b) – S(a –
1)
Вычисление чисел
Фибоначчи через формулу Бине
Рассмотрим
производящую функцию для чисел Фибоначчи (F0 = 0, F1
= 1):
G(x) = 
= F0 + F1x
+ 
=
F0 + F1x
+ 
=
x + 
+ 
=
x + 
+ 
=
x + xG(x) + x2G(x)
Отсюда:
G(x) (1 – x
– x2) = x,
G(x) = 
Разложим
производящую функцию на простые дроби. Найдем корни знаменателя:
1 – x – x2
=
(1 – φx) (1 – ψx),
где
φ = 
, ψ = 
Теперь
представим производящую функцию в виде:
= 
+ 
Решая систему,
получим:
A = 
, B = 
Учитывая что
= 
,
производящую
функцию можно переписать в виде:
G(x) = 
= 
Но поскольку
G(x) =
то приравнивая
коэффициенты при xn, получим:
= 
= 
Вычисление чисел
Фибоначчи через тождество
Для чисел Фибоначчи
известно следующее тождество:
Fn+m
= Fm ∙ Fn+1 + Fm-1
∙ Fn
Из него непосредственно
следуют частные случаи:
·
если m = n, то F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn
·
если m = n + 1, то F2n+1 = Fn+1
∙ Fn+1 + Fn ∙ Fn
Эти формулы позволяют
вычислять числа Фибоначчи методом “разделяй и властвуй”, сводя вычисление Fn к значениям с примерно
вдвое меньшими индексами.
Отдельно обрабатываются
базовые случаи:
F0 =
0, F1 =
F2 = 1
Благодаря такому подходу
глубина рекурсии пропорциональна log2n,
а временная сложность алгоритма составляет O(log2n).
Пример
Вычислим
несколько чисел Фибоначчи по формуле Бине, работая в расширенном поле 
по большому модулю p.
= 
= 
= 
= 
= 1
= 
= 
= 
= 
= 2
= 
= 
= 
= 
= 3
Рассмотрим на
примере выполнение формул:
·
если m = n, то F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn
·
если m = n + 1, то 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
Реализация алгоритма
Объявим константу MOD, по модулю которой будут производиться
вычисления.
#define MOD 1000000007
Объявим переменную fib типа map для запоминания
уже вычисленных чисел Фибоначчи.
map<long long, long long>
fib;
Функция f вычисляет n-е число
Фибоначчи по модулю MOD.
long long f(long long n)
{
if (n ==
0) return 0;
if (n ==
1) return 1;
if (n ==
2) return 1;
Если n-е число Фибоначчи уже было вычислено ранее и сохранено в fib, оно возвращается
сразу, без повторных вычислений.
if (fib[n]) return fib[n];
Далее
используем разложение числа n на:
·
n = 2k + 1 – нечётный случай: 
.
·
n = 2k – чётный случай: 
.
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);
Реализация алгоритма – формула Бине
Объявим константу MOD, по модулю которой будут производиться
вычисления.
#define MOD 1000000007
Объявим
структуру Num для хранения
числа вида 
.
struct Num
{
long long x, y; // x + y*sqrt(5)
Num(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};
Реализуем умножение в поле . Функция 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;
}
Функция pow реализует возведение в степень basen, где base – число в поле .
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;
}
Функция modpow вычисляет
значение 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;
}
Функция fib вычисляет n-ое число
Фибоначчи.
long long fib(long long n)
{
Инициализируем
константы φ = 1 + 
и ψ = 1 – .
Num phi(1, 1);
Num psi(1, MOD - 1);
Вычисляем степени A = φn и B = ψn.
Num A = pow(phi, n);
Num B = pow(psi, n);
Поскольку
= = = 
,
вычисляем отдельно числитель и знаменатель.
Отметим, что 
= 
(поэтому – = 0), а коэффициент при в числителе равен 
– 
.
long long numerator = (A.y - B.y
+ MOD) % MOD;
Вычисляем 2n в
знаменателе.
long long denom = pow(2, n);
Числитель и знаменатель содержат множитель .
Сократим дробь на него. Теперь остается вычислить результат, который равен
= numerator * 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);