duckladydinh's blog

Help! Divide and Conquer Algorithm for Computing General Linear Recurrence???
By duckladydinh, history, 7 years ago, In English

Hallo, everyone.

Can you please help me with the following problem?

If a[n] = b[k] * a[n-k] for k = 1..n, then the generating function A(x) = a[0] / (1 — B(x)) We can compute all a[n] with Divide and Conquer algorithm in O(nlog^2(n)). What is that Divide and Conquer algorithm?

I have the feeling that it is strongly related to FFT but that's just my feeling. Can someone give me the exact algorithm?

Thank you

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Do you mean a[N] = a[N - k] * b[k] for k = 1 to n, where you are given first n terms of a and b, and you want Nth term of a? In other words, a is a linear recurrence, and you want Nth term.
But if you are doing a[n] = b[k] * b[n-k], isn't it just convolution of b with itself? Which can be done in using FFT.

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

    ah so true. It is a typing mistake!!! It is b[k] * a[n-k] for k = 1..n

    and also, I want to compute all a[n] faster than O(n^2). Otherwise, isn't it good enough to use just a nested loop :D

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

Call the Convolution function here with both array being b[]. It will return what you want in .

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

    Sorry it is a typing mistake, it should be a[n-k]*b[k].

    And even if it is b[i] * b[n — i], I would like to compute the n-th element in O(nlogn or something time). Since if i have the array b[1..n-1] already, just a linear loop can compute b[n]

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

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The divide-and-conquer algorithm for this problem works as follows:

solve(l, r): // calculate all values a[i] in [l, r)
    if l + 1 == r: return
    m = (l + r) / 2
    solve(l, m) // recursively solve for the left half
    c = a[l .. m-1] * b[1 .. m-l] // calculate convolution of left half of A and B using FFT
    for i = 0..(r - m):
        a[m + i] += c[m - l + i] // add contribution of the left half a[l..m) to the right half a[m..r)
    solve(m, r) // recursively solve for the right half

Indices might be wrong at some places, but the idea is like this.

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

    Thank you. I am not exactly clear, but your pseudo code looks very promising. I mean I think I get the picture now. :D Thanks

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It can be done in as described here: http://codeforces.me/blog/entry/12513, last problem.

→ Reply