Доброго времени суток!
Сегодня я хотел бы рассказать о методе разрешения некоторых рекуррентностей и разобрать классический пример на эту тему.
Начнем с определения рекуррентной формулы:
Рассмотрим задачу, которая формулируется очень просто: нам нужно найти 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). Пусть у нас есть вектор столбец , — n-ое число Фибоначчи, постараемся подобрать оператор такой, что будет выполняться равенство . Для чисел Фибоначчи легко найти матрицу этого оператора, если вспомнить рекуррентную формулу , матрица равна , действительно . А учитывая то, что наш оператор подходит не только для первых чисел Фибоначчи, а и для всех, то есть , имеем . Значит мы можем вычислить ответ, возведя матрицу нашего оператора в N-ую степень, для этого воспользуемся алгоритмом логарифмического возведения в степень. Вот код, написанный на java:
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));
Спасибо за внимание.