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, or in this case of: (a1*x^k + a2* x^(k-1) + .... + ak) * (b1*x^k + .... + bk) * (c1*x^k + ... + ck) * ..... (n polymials of x^k)

Where O((n*k)log(n*k)) is on the verge of risking TLE

I wonder if it is possible to trim the terms so that we don't have to evaluate beyond k <= 2^i terms as if we are convoluting the polynomials with brute force.

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.