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

Последние цифры и ДП

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

Не вычисляем гигантские степени
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 на обычное вычисление огромной степени.
Печать