дискретная-математика - Предложите непереборный алгоритм

Это можно сделать при помощи производящих функций (даже для более общего случая). Нас интересует число решений уравнения $%x+2y+5z=n$% в целых неотрицательных числах. Обозначим эту величину через $%a_n$%.

Рассмотрим такое произведение трёх бесконечных рядов: $%(1+t+t^2+\cdots)(1+t^2+t^4+\cdots)(1+t^5+t^{10}+\cdots)$%. Если в нём раскрыть скобки, то коэффициент при $%t^n$% окажется равен в точности $%a_n$%. Это следует из того, что из первой скобки мы берём какое-то $%t^x$%, из второй $%t^{2y}$%, из третьей $%t^{5z}$%. После перемножения получается $%t^{x+2y+5z}=t^n$%, и такой одночлен встречается ровно столько раз, сколько решений имеет наше уравнение. То есть он будет иметь коэффициент $%a_n$% после приведения подобных членов.

Теперь заметим, что каждый сомножитель представляет собой сумму бесконечной геометрической прогрессии, и если применить соответствующую формулу, то получится $%\frac1{1-t}\cdot\frac1{1-t^2}\frac1{1-t^5}=\frac1{(1-t)(1-t^2)(1-t^5)}=\frac1{1-t-t^2+t^3-t^5+t^6+t^7-t^8}$%.

Далее, если мы начнём делить "столбиком" многочлен 1 на многочлен в знаменателе, то у нас получится ряд вида $%a_0+a_1t+a_2t^2+\cdots+a_nt^n+\cdots$%, где $%a_0=1$%, а следующие числа получаются из предыдущих по рекуррентной формуле $%a_n=a_{n-1}+a_{n-2}-a_{n-3}+a_{n-5}-a_{n-6}-a_{n-7}+a_{n-8}$%. Применять её можно при всех $%n\ge1$%, считая, что члены с отрицательными номерами равны нулю.

Этот метод применим и к более сложным ситуациям, но для задачи из условия есть ещё более простой подход. Прежде всего, легко заметить, что уравнение $%x+2y=k$% при фиксированном $%k$% имеет ровно $%\left\lfloor{\frac{k}2}\right\rfloor+1$% решение. Действительно, можно брать любое $%y$%, удовлетворяющее неравенству $%0\le y\le\frac{k}2$%, поскольку $%x$% однозначно выражается по формуле $%x=k-2y$%.

Теперь, решая уравнение $%x+2y+5z=n$%, мы придаём переменной $%z$% все значения от 0 до $%\left\lfloor{\frac{n}5}\right\rfloor$%, и далее по всем таким $%z$% суммируем величины вида $%\left\lfloor{\frac{n-5z}2}\right\rfloor+1$%. Это также даёт быстрый алгоритм вычисления. Например, сколькими способами можно разменять 50 рублей? Это число $%a_{50}$%, равное $%(\left\lfloor{\frac{50}2}\right\rfloor+1)+(\left\lfloor{\frac{45}2}\right\rfloor+1)+\cdots+(\left\lfloor{\frac{0}2}\right\rfloor+1)=26+23+21+18+16+13+11+8+6+3+1=146$%.