Hi codeforces! I want to show that how to implement the algorithm from noshi91 who showed that we could modify the Bostan--Mori's algorithm to make use in FPS composition and compositional inverse.
noshi91's blog: FPS の合成と逆関数、冪乗の係数列挙 Θ(n (log(n))^2) in Japanese.
UPD: my submission. relative code from line 874 to 923.
Compositional Inverse
The key idea is consider the bivariate formal power series
Let $$$f(0)=0$$$, we have
Apply Bostan--Mori's algorithm here:
so
The degree of $$$y$$$ doubled after each time of iteration, but the degree of $$$x$$$ halved.
Combined with Lagrange Inversion Formula, we have the following algorithm:
Composition
Given $$$f=\sum_{k\geq 0}f_kx^k\in\mathbb{C}\left\lbrack\left\lbrack x\right\rbrack\right\rbrack,g\in x\mathbb{C}\left\lbrack\left\lbrack x\right\rbrack\right\rbrack$$$ then
Consider again
Our goal is computing
Apply Bostan--Mori's algorithm here:
We want to compute $$$\dfrac{P(y)}{Q(x,y)Q(-x,y)}$$$ first, and we only need to track finitly many coefficients of $$$y^j$$$ for $$$j\leq 0$$$.
and the composition algorithm is just
One can try with composition_of_formal_power_series_large at Library Checker.