haleyk100198's blog

Is it possible to trim FFT processed term without inversing it?
By haleyk100198, history, 7 years ago, In English

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^2(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.

Tags fft
  • Vote: I like it
  • +26
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand what do you want to do :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In short, my aim is to find the x^k term of

    (x+a) * (x+b) * (x+c) * ... (x+z)

    In trivial case this can be done by just merging the elements with FFT, as if the elements are leafs of a segment tree:

    (Picture made by Al.Cash)

    So at each layer the power of the polymial will grow by a factor of 2. Yet, we know that terms larger than x^k is no influence on the final answer, and if k is given to be a rather small number, it may be a wise idea to just trim the polymial, and don't care about stuff beyond x^k.

    This brings me thinking if there's a convenient way of deleting elements larger than x^k for terms that have gone through FFT, as I reckon that the terms are inter-related.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So why don't you use solution using this tree?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am just curious if there exists a way to take advantage of the small k in case if I am facing some other weird situations. (Though I understand O(nlog^2n) is decent enough in most situations)

        → Reply