Problem

Given (x+a1) * (x+a2) * (x+a3) * ... * (x+an), find the coefficient of the term x^k.

In the case of n, k <= 10^5, one way to approach the problem is to use FFT to convolute the terms layer by layer, by eventually raising the maximum power of the terms. (i.e. evaluate the terms grouped in two, four, eight etc. terms) The time complexity of this approach is around O(N*log^2(N)).

In another case where k << n, where k is way smaller than n, I wonder if it is possible to trim the terms so that we don't have to evaluate beyond k <= 2^i terms. (While I am aware that this doesn't matter a lot in this scenario, but who knows wicked stuff will some others come up with) As all the original terms have effect on all values after FFT, I assume that one could not naively extract the least significant 2^i terms from the FFT array, so inverse FFT should be applied before trimming (And O(nlogn) isn't too expensive anyways). Yet, I would like to know if there exist an approach which works around this step.

Inspired by: https://www.hackerrank.com/challenges/permutation-equations

There exists a solution which involves finding the coefficient of (x+n-2) * (x+n-1) * ... (x+2) where k <= 60.