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
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.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
Call the
Convolution
function here with both array beingb[]
. It will return what you want in .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]
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
The divide-and-conquer algorithm for this problem works as follows:
Indices might be wrong at some places, but the idea is like this.
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
It can be done in as described here: http://codeforces.net/blog/entry/12513, last problem.