Доброго времени суток!
Сегодня я хотел бы рассказать о методе разрешения некоторых рекуррентностей и разобрать классический пример на эту тему.
Начнем с определения рекуррентной формулы:
Рассмотрим задачу, которая формулируется очень просто: нам нужно найти N-ое число Фибоначчи по модулю P, где N <= 10^15, P <= 10^9. Как видно из ограничений, складывать числа тривиальным методом за О(n) не получится, нужно придумывать более быстрый алгоритм, в этой статье речь пойдет об операторном методе с асимптотикой O(log N). Пусть у нас есть вектор столбец
,
— n-ое число Фибоначчи, постараемся подобрать оператор
такой, что будет выполняться равенство
. Для чисел Фибоначчи легко найти матрицу этого оператора, если вспомнить рекуррентную формулу
, матрица равна
, действительно
. А учитывая то, что наш оператор подходит не только для первых чисел Фибоначчи, а и для всех, то есть
, имеем
. Значит мы можем вычислить ответ, возведя матрицу нашего оператора в N-ую степень, для этого воспользуемся алгоритмом логарифмического возведения в степень. Вот код, написанный на java:
Осталось только выдать наш ответ:
Спасибо за внимание.
Сегодня я хотел бы рассказать о методе разрешения некоторых рекуррентностей и разобрать классический пример на эту тему.
Начнем с определения рекуррентной формулы:
Рекуррентная формула — формула вида ![]() ![]() ![]() |
Рассмотрим задачу, которая формулируется очень просто: нам нужно найти N-ое число Фибоначчи по модулю P, где N <= 10^15, P <= 10^9. Как видно из ограничений, складывать числа тривиальным методом за О(n) не получится, нужно придумывать более быстрый алгоритм, в этой статье речь пойдет об операторном методе с асимптотикой O(log N). Пусть у нас есть вектор столбец
![](http://s45.radikal.ru/i108/1004/41/616f58b16752.gif)
![](http://s57.radikal.ru/i155/1004/6d/823c6ac2fdf7.gif)
![](http://s55.radikal.ru/i150/1004/c7/15854bcc00e0.gif)
![](https://habrastorage.org/getpro/habr/post_images/b6e/1bc/06e/b6e1bc06ed80b284a34d6c83c2f8000f.gif)
![](http://s51.radikal.ru/i131/1004/64/166f2d59b5f8.gif)
![](http://s004.radikal.ru/i206/1004/b5/93cdc5f53324.gif)
![](https://habrastorage.org/getpro/habr/post_images/36e/b75/a44/36eb75a44bf94237acef64fe4e9b68fb.gif)
![](https://habrastorage.org/getpro/habr/post_images/5a2/533/dc6/5a2533dc633f772444c58f6a3c10634c.gif)
![](http://i060.radikal.ru/1004/e3/96a194c6950e.gif)
Copy Source | Copy HTML
- private static long getFibb(int n) {
- long a11 = 1, a12 = 1, a21 = 1, a22 = 0; //матрица оператора
- long r11 = 1, r12 = 0; //вектор-столбец результа
- long q11 = 0, q12 = 0, q21 = 0, q22 = 0; //вспомогательная матрица при перемножении
- while (n > 0) {
- if ((n&1)==1) {
- q11 = (r11 * a11 + r12 * a21) % MOD;
- q12 = (r11 * a12 + r12 * a22) % MOD;
- r11 = q11;
- r12 = q12;
- }
- q11 = (a11 * a11 + a12 * a21) % MOD;
- q12 = (a11 * a12 + a12 * a22) % MOD;
- q21 = (a21 * a11 + a22 * a21) % MOD;
- q22 = (a21 * a12 + a22 * a22) % MOD;
- a11 = q11;
- a12 = q12;
- a21 = q21;
- a22 = q22;
-
- n >>= 1;
- }
- return r12; //возвращаем Fn
- }
Осталось только выдать наш ответ:
Copy Source | Copy HTML
- out.println(getFibb(N));
Спасибо за внимание.