By duckladydinh, history, 7 years ago,

Hallo, everyone.

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

• +2

 » 7 years ago, # | ← Rev. 3 →   0 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 ah so true. It is a typing mistake!!! It is b[k] * a[n-k] for k = 1..nand 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
 » 7 years ago, # |   0 Call the Convolution function here with both array being b[]. It will return what you want in .
•  » » 7 years ago, # ^ |   0 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]
 » 7 years ago, # |   0 Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
 » 7 years ago, # |   +8 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.
•  » » 7 years ago, # ^ |   0 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
 » 7 years ago, # |   +5 It can be done in as described here: http://codeforces.com/blog/entry/12513, last problem.