Python
# Способ 1 — рекурсия (на слабых компах не потянет)
from sys import *
setrecursionlimit(1000000)
def f(n):
if n < 5: return n
return 2 * n * f(n - 4)
print((f(13766) - 9*f(13762)) // f(13758))
# Способ 2 — кэширование (lru_cache)
from functools import lru_cache
@lru_cache(None)
def f(n):
if n < 5: return n
return 2 * n * f(n - 4)
for i in range(14000): f(i) # заполняем кэш
print((f(13766) - 9*f(13762)) // f(13758)) Способ 2
# Способ 3 — мемоизация через список (самый быстрый)
f = [0] * 14000
for n in range(len(f)):
if n < 5:
f[n] = n
if n >= 5:
f[n] = 2 * n * f[n - 4]
print((f[13766] - 9*f[13762]) // f[13758])📚 Теория
Рекуррентные соотношения. Оптимизация через кэширование.