Hi
I am learning FFT. ChatGPT told me that FFT could assist in solving self-convolution form like Catalan number where the (n+1)-th element is some convolution of the first n elements. For example:
c[n + 1] = sum(c[i][n — i]) for i in 0..n
Unfortunately, no matter where I look (and how hard I press ChatGPT), I couldn't find a single website/book/paper detailing this approach.
My Question: Is it actually possible to compute the first n elements of a self-convolution form like Catalan using FFT in, for example, O(nlogn) or less than O(n^2)?
Thanks a lot
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
On Codeforces (and in competitive programming) this is usually known as 'Online FFT'. You should be able to find CF blog posts on this topic solving it in $$$O(n\log^2{n})$$$.
The link is here: CDQ convolution (online FFT) generalization with Newton method
Suppose we have
Then the generating function A(x) satisfies A=ABx+c and therefore we may invert 1-Bx to find a in O(nlogn).