Is it possible to trim FFT processed term without inversing it?

Revision en1, by haleyk100198, 2017-07-22 21:46:35

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.

Tags fft

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English haleyk100198 2017-07-23 05:06:15 2 (published)
en2 English haleyk100198 2017-07-22 21:56:39 312
en1 English haleyk100198 2017-07-22 21:46:35 1426 Initial revision (saved to drafts)