The problem I was trying to solve is this:
A thief made his way to a shop.
As usual he has his lucky knapsack with him. The knapsack can contain $k$ objects. There are $n$ kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind $i$ is $a_i$.
The thief is greedy, so he will take exactly $k$ products (it's possible for some kinds to take several products of that kind).
Find all the possible total costs of products the thief can nick into his knapsack.
The solution described is as follows:
Let $k = 2$, then this is the standard problem that can be solved with the help of FFT (fast Fourier transform). And it is solved as follows: consider a polynomial in which the coefficient of the $i^{th}$ power is equal to one if and only if in the given array there is a number $i$. Let's raise this polynomial to a square, then those $i$ coefficient for which the squared is not equal to $0$ will be in the answer. It is easy to generalize this solution to the case of an arbitrary $k$. You just need to raise the initial polynomial to the $k^{th}$ power. This, of course, needs to be done with the help of binary exponentiation. The complexity is $O(WlogWlogk)$, where $W$ is the maximum sum.
I have no idea why this works so I need some explanation about it. Thanks.