Сегодня на контест мы дали задачку про обратный рюкзак.

Мы, кроме того, умеем почти так же решать обычный рюкзак с бесконечными предметами, если решить его для отрезка [1..m], то есть получить многочлен с коэффициентами 1 там, где можно получить такую сумму и 0 — там где нельзя. К этому многочлену нужно на отрезкок [m+1..2m] добавить единицы в те позиции, где есть предметы. Потом полученный многочлен возвести в квадрат. Тогда мы решили задачу за . Мне интересно, это боян?

UPD: это все бред, недостаточно просто возводить в квадрат =(

UPD: но достаточно два раз возвести в квадрат!