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