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 firstnterms ofaandb, and you wantN^{th}term ofa? In other words,ais a linear recurrence, and you wantN^{th}term.But if you are doing

`a[n] = b[k] * b[n-k]`

, isn't it just convolution ofbwith 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 being`b[]`

. 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.com/blog/entry/12513, last problem.