Статья Автор: Деникина Н.В., Деникин А.В.

Рекуррентные функции — Последние цифры и ДП


Громадное F(n), но нужны только последние цифры

SilverTests № 82652

Не вычисляем гигантские степени
F(n) = nⁿ, если n > 450000; F(n) = 3n + F(n + 14) + 2 · F(n + 7), если n ≤ 450000.

Найдите последние 6 цифр F(73137).

Сохраняем только остатки по модулю 10**6. Для степеней используем pow(n, n, MOD), чтобы не создавать огромное целое число.


Как заполнять

В формуле нужны большие аргументы n+7 и n+14. Значит, значения рассчитываем от больших n к маленьким.

Почему шаг 7

Все аргументы имеют один остаток при делении на 7. Считаем только соответствующую цепочку, а не все натуральные числа.



Отбрасывать старшие цифры после каждого шага можно, потому что в рекуррентной формуле использованы только сложение и умножение. Не заменяйте n**n на обычное вычисление огромной степени.
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать