Hi everyone!↵
↵
This is yet another blog that I had drafted for quite some time, but was reluctant to publish. I decided to dig it up and complete to a more or less comprehensive state for the [$300 contest](https://mirror.codeforces.com/blog/entry/110840).↵
↵
Essentially, the blog tells how to combine CDQ technique for relaxed polynomial multiplication ("online FFT") with linearization technique from Newton method (similar approach is used in the first example of the [ODE blog post](https://mirror.codeforces.com/blog/entry/76447) by [user:amiya,2023-01-14]), so that the functions that typically require Newton's method can be computed online as well. I will try to briefly cover the general idea of "online FFT" too and provide some examples, in case you're not well familiar with it. That being said...↵
↵
[cut]↵
<hr>↵
↵
Consider the following setting:↵
↵
There is a differentiable function $F(x)$ such that $F(0)=0$ and a polynomial $f(x)$.↵
↵
You want to compute first $n$ coefficients of a formal power series $g(x)$ such that $g(x) = F(f(x))$. However, the series $f(x)$ is not known in advance. Instead, the $k$-th coefficient of $f(x)$ is given to us after we compute the $k$-th coefficient of $g(x)$.↵
↵
Looks familiar? No? Ok, let's make a brief detour first.↵
↵
## CDQ convolution↵
↵
General idea of [CDQ technique](https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html) is described in the following simple scheme: To compute something on the $[l,r)$ interval,↵
↵
1. Compute it on $[l, m)$ for $m=\frac{l+r}{2}$,↵
2. Compute the influence of $[l, m)$ onto $[m,r)$,↵
3. Compute everything else in $[m, r)$ recursively,↵
4. Merge the results.↵
↵
This approach is very versatile, and In convolution context, it's commonly known as "[online FFT](https://tanujkhattar.wordpress.com/2018/01/03/online-fft/)". It has the following typical formulation:↵
↵
### Standard formulation↵
↵
We want to compute a sequence $c_0, c_1, \dots, c_n$, such that↵
↵
$$↵
c_k = \sum\limits_{i+j=k-1} a_i b_j,↵
$$↵
↵
where $a_0, a_1, \dots, a_n$ and $b_0, b_1, \dots, b_n$ are not known in advance, but $a_k$ and $b_k$ are revealed to us after we compute $c_k$.↵
↵
In a more polynomial-like manner, we may formulate it as↵
↵
$$↵
C(x) = x A(x) B(x),↵
$$↵
↵
where the $k$-th coefficient of the polynomials $A(x)$ and $B(x)$ is revealed to us as we compute the $k$-th coefficient of $C(x)$.↵
↵
### Examples↵
↵
**Polynomial exponent**. Assume you want to compute $Q(x)=e^{P(x)}$ for a given $P(x)$.↵
↵
<spoiler summary="reduction">↵
Typical way to do it in $O(n \log n)$ is to use the Newton's method on the equation above, formulated through logarithms. It is not very practical because of a very high constant factor. However, if you differentiate $Q(x)$, you get the following equation:↵
↵
$$↵
xQ' = xP' Q↵
$$↵
↵
The polynomial $xP'(x)$ is known in advance, and the $k$-th coefficient of $Q(x)$ can be computed once you know the $k$-th coefficient of $xQ'(x)$, thus the setting mentioned above applies.↵
</spoiler>↵
↵
**[Jetpack](https://csacademy.com/contest/archive/task/jetpack/)**. You want to get from $(0, 0)$ to $(n, 0)$. On each step, you increase you $x$-coordinate by $1$, and your $y$ coordinate changes to $y+1$ if you use the jetpack or to $\max(0, y-1)$ if you don't. At the same time, you can only have $y > 0$ for at most $2k$ steps. How many ways are there to get to $(n, 0)$ under the given constraints?↵
↵
<spoiler summary="reduction">↵
This is the first problem that I know in which such technique appeared. Let $\operatorname{dp}[i]$ be the number of ways to get from $(0, 0)$ to $(i, 0)$ in such a way that you have just landed in $(i, 0)$. If the previous landing point was $i-j$, there are $\operatorname{catalan}[j/2-1]$ ways to go from $i-j$ to $i$ without intermediate landings if $j$ is even, and $0$ otherwise, thus we may define↵
↵
$$↵
\operatorname{coef}[j] = \begin{cases}↵
\operatorname{catalan}[j/2-1] & 2 \leq j \leq 2k\text{ is even},\\↵
0 & j\text{ is odd or }j \not\in[2,2k]↵
\end{cases}↵
$$↵
↵
and↵
↵
$$↵
\operatorname{sum}[i] = \operatorname{dp}[0] + \dots + \operatorname{dp}[i].↵
$$↵
↵
Then, we can see the explicit convolution:↵
↵
$$↵
\operatorname{dp}[i] = \sum\limits_{j=0}^{i} \operatorname{sum}[i-j] \cdot \operatorname{coef}[j].↵
$$↵
↵
Let $D(x)$ be the generating function for $\operatorname{dp}$, $C(x)$ the generating function for $\operatorname{coef}$ and $S(x) = \frac{D(x)}{1-x}$ be the generating function for $\operatorname{sum}$. Then the convolution above rewrites as follows:↵
↵
$$↵
D(x) = \frac{D(x)}{1-x} \cdot C(x) + 1,↵
$$↵
↵
thus↵
↵
$$↵
D(x) = \frac{1-x}{1-x-C(x)}.↵
$$↵
↵
Wait, that's an exact solution and can be computed in $O(n \log n)$. Oh no, overkill... Let's go back to $D(x) = S(x) C(x)+1$. As you may see, $C(x)$ is divisible by $x$, and we may rewrite the task as↵
↵
$$↵
D(x) - 1 = x S(x) P(x), ↵
$$↵
↵
where again $P(x)=\frac{C(x)}{x}$ is known in advance and $S(x)$ can be computed from $D(x)-1$ after a new coefficient of it is known.↵
</spoiler>↵
↵
**[Gennady Korotkevich Contest 5 — Bin](https://www.acmicpc.net/problem/18743)**. Find the number of full binary trees with $n$ leaves such that for every vertex with two children, the number of leaves in its left sub-tree doesn’t exceed the number of leaves in its right sub-tree by more than $k$.↵
↵
<spoiler summary="reduction">↵
It's not hard to see that if $T_n$ is the number of such trees, then↵
↵
$$↵
T_n = \sum\limits_{\substack{i+j=n \\ j \leq i + k}} T_i T_j↵
$$↵
↵
with the base case $T_0=0$ and $T_1=1$. One possible way to solve it is to note that↵
↵
$$↵
T_n = \sum\limits_{\substack{i+j=n \\ j < i}} T_i T_j + \sum\limits_{\substack{i+j=n \\ i \leq j \leq i + k}} T_i T_j↵
$$↵
↵
Let $T(x)$ be the generating function of $T_n$ and $D(x)$ be the generating function of↵
↵
$$↵
D_n = T_n - \sum\limits_{\substack{i+j=n \\ i \leq j \leq i + k}} T_i T_j,↵
$$↵
↵
then the recurrence relation is↵
↵
$$↵
D_n = \sum\limits_{\substack{i+j=n \\ j < i}} T_i T_j,↵
$$↵
↵
but in terms of generating functions it rewrites as↵
↵
$$↵
D(x) = \frac{T^2(x) - T(x^2)}{2},↵
$$↵
↵
and to make it a bit more pretty↵
↵
$$↵
2D(x) + T(x^2) = T^2(x).↵
$$↵
↵
Note that $T(x)$ is divisible by $x$ because $T_0=0$, and knowing the $k$-th coefficient of $2D(x)+T(x^2)$ we may as well get the $k$-th coefficient of $T(x)$ from the definition of $D_n$, making CDQ technique applicable.↵
</spoiler>↵
↵
### Solution↵
↵
Okay, how to solve this? Let's recall the convolution formula↵
↵
$$↵
c_k = \sum\limits_{i+j=k-1} a_i b_j.↵
$$↵
↵
Assume that we want to compute $c_k$ for $k$ in $[l, r)$ and we already know values of $c_k$,We need to figure out what $a_i$ and $b_j$ for $i, j, k \in [l, m)$. Consider the contributione to $c_k$it for $k \in [m, r)$ of $(i, j)$ pairs such that both $i$ and $j$ are below $m$ and at least one of them is above or equal to $l$. For each such $a_i$, values of interest for $j$ range from $0$ to $\min(m, r-l)$.↵
↵
Correspondingly, for each $b_j$, values of interest. We can rewrite it as:↵
$$↵
\sum\limits_{i+j=k} a_i b_j = \dots +\sum\limits_{i=l}^m a_i b_{k-i} + \sum\limits_{j=l}^m b_j a_{k-j}↵
$$↵
In the formula above, the first sum only needs $b_j$ for $j$ from $0$ to $\min(m, r-l)$, as values above $m$ will be accounted for elsewhere, and values above $r-l$ do not occur in the sum.↵
↵
Similar holds for the second sum. However, to avoid double-counting $a_i b_j$ when both $i, j \in [l, m)$, we only consider $a_i$ for $i$range from $0$ to $\min(l, r-l)$. In both cases, the contribution may be computed with an appropriate convolution of polynomials of size at most $r-l$. Note that in the second case we used $\min(l, r-l)$ instead of $er words, we update $c[m, r)$ with the following:↵
↵
- Convolution of $a[l, m)$ with $b[0, \min(m, r-l))$ to avoid double-counting pairs in which both $i$ and $j$ are $l$ or above.↵
↵
W,↵
- Convolution of $b[l, m)$ with $a[0, \min(l, r-l))$.↵
↵
Overall, we make two recursive calls and use extra $O(n \log n)$ time to consolidate them, making itfor overall $O(n \log^2 n)$ time. The time can be improved by roughly 50 %, if one of the inputs is fully known in advance, rather than online.↵
↵
## Generalization↵
↵
Now back to the beginning. The examples above typically expect that the right-hand side is formulated in a way that is kind of similar to convolutions. But there are a lot of functions, for which it's not really possible to do so. Try the following ones in a similar setting (i.e. the coefficients of $f(x)$ are given after the coefficients of $g(x)$ are computed):↵
↵
$$\begin{gather}↵
g(x) =& x \cdot e^{f(x)} \\ \\↵
g(x) =& x \cdot \log \frac{1}{1-f(x)} \\ \\↵
g(x) =& x \cdot \frac{1}{1-f(x)}↵
\end{gather}$$↵
↵
Those are the functions that are quite typical in formal power series (for their interpretation, see [here](https://mirror.codeforces.com/blog/entry/103979)). You may probably rephrase them in a convolution-like manner, so that CDQ is applicable, but you would need to do something ad hoc for each individual function. It doesn't seem very convenient, so it only makes sense to try and find some generic enough approach. What is a generic formulation here?↵
↵
$$↵
g(x) = F(f(x)).↵
$$↵
↵
And you may note that what all these functions $F(\dots)$ have in common is that they're differentiable. Let's use it in a similar way to what we do in Newton's method and rewrite the right hand side in the following way:↵
↵
$$↵
g(x) = F(f_0) + F'(f_0) (f - f_0) + O((f-f_0)^2). ↵
$$↵
↵
This formula generally works for any $f_0$. In particular, let $f_0$ be first $n$ coefficients of $f$, then $(f-f_0)^2$ is divisible by $x^{2n}$. In other words,↵
↵
$$↵
g(x) \equiv F(f_0) + F'(f_0) (f - f_0) \pmod{x^{2n}}.↵
$$↵
↵
In this formula, we still do not know $f(x)$ completely. But what's important is that it is no longer an argument of some generic function $F(\dots)$, so the right-hand side is now a linear function of $f(x)$! This is exactly the formulation for which we learned to apply CDQ convolution above, that is $g(x) = A(x) f(x) + B(x)$, where↵
↵
$$\begin{gather}↵
A(x) =& F'(f_0), \\ \\↵
B(x) =& F(f_0) - f_0 F'(f_0)↵
\end{gather}$$↵
↵
are specific constant polynomials in this context. This sub-problem is solvable in $O(n \log^2 n)$ with the standard CDQ technique, and since it allows us to double the number of known coefficients at each step, the overall running time is also $O(n \log^2 n)$, assuming that we're able to compute $F(\dots)$ and $F'(\dots)$ in $O(n \log^2 n)$ as well.
↵
This is yet another blog that I had drafted for quite some time, but was reluctant to publish. I decided to dig it up and complete to a more or less comprehensive state for the [$300 contest](https://mirror.codeforces.com/blog/entry/110840).↵
↵
Essentially, the blog tells how to combine CDQ technique for relaxed polynomial multiplication ("online FFT") with linearization technique from Newton method (similar approach is used in the first example of the [ODE blog post](https://mirror.codeforces.com/blog/entry/76447) by [user:amiya,2023-01-14]), so that the functions that typically require Newton's method can be computed online as well. I will try to briefly cover the general idea of "online FFT" too and provide some examples, in case you're not well familiar with it. That being said...↵
↵
[cut]↵
<hr>↵
↵
Consider the following setting:↵
↵
There is a differentiable function $F(x)$ such that $F(0)=0$ and a polynomial $f(x)$.↵
↵
You want to compute first $n$ coefficients of a formal power series $g(x)$ such that $g(x) = F(f(x))$. However, the series $f(x)$ is not known in advance. Instead, the $k$-th coefficient of $f(x)$ is given to us after we compute the $k$-th coefficient of $g(x)$.↵
↵
Looks familiar? No? Ok, let's make a brief detour first.↵
↵
## CDQ convolution↵
↵
General idea of [CDQ technique](https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html) is described in the following simple scheme: To compute something on the $[l,r)$ interval,↵
↵
1. Compute it on $[l, m)$ for $m=\frac{l+r}{2}$,↵
2. Compute the influence of $[l, m)$ onto $[m,r)$,↵
3. Compute everything else in $[m, r)$ recursively,↵
4. Merge the results.↵
↵
This approach is very versatile, and In convolution context, it's commonly known as "[online FFT](https://tanujkhattar.wordpress.com/2018/01/03/online-fft/)". It has the following typical formulation:↵
↵
### Standard formulation↵
↵
We want to compute a sequence $c_0, c_1, \dots, c_n$, such that↵
↵
$$↵
c_k = \sum\limits_{i+j=k-1} a_i b_j,↵
$$↵
↵
where $a_0, a_1, \dots, a_n$ and $b_0, b_1, \dots, b_n$ are not known in advance, but $a_k$ and $b_k$ are revealed to us after we compute $c_k$.↵
↵
In a more polynomial-like manner, we may formulate it as↵
↵
$$↵
C(x) = x A(x) B(x),↵
$$↵
↵
where the $k$-th coefficient of the polynomials $A(x)$ and $B(x)$ is revealed to us as we compute the $k$-th coefficient of $C(x)$.↵
↵
### Examples↵
↵
**Polynomial exponent**. Assume you want to compute $Q(x)=e^{P(x)}$ for a given $P(x)$.↵
↵
<spoiler summary="reduction">↵
Typical way to do it in $O(n \log n)$ is to use the Newton's method on the equation above, formulated through logarithms. It is not very practical because of a very high constant factor. However, if you differentiate $Q(x)$, you get the following equation:↵
↵
$$↵
xQ' = xP' Q↵
$$↵
↵
The polynomial $xP'(x)$ is known in advance, and the $k$-th coefficient of $Q(x)$ can be computed once you know the $k$-th coefficient of $xQ'(x)$, thus the setting mentioned above applies.↵
</spoiler>↵
↵
**[Jetpack](https://csacademy.com/contest/archive/task/jetpack/)**. You want to get from $(0, 0)$ to $(n, 0)$. On each step, you increase you $x$-coordinate by $1$, and your $y$ coordinate changes to $y+1$ if you use the jetpack or to $\max(0, y-1)$ if you don't. At the same time, you can only have $y > 0$ for at most $2k$ steps. How many ways are there to get to $(n, 0)$ under the given constraints?↵
↵
<spoiler summary="reduction">↵
This is the first problem that I know in which such technique appeared. Let $\operatorname{dp}[i]$ be the number of ways to get from $(0, 0)$ to $(i, 0)$ in such a way that you have just landed in $(i, 0)$. If the previous landing point was $i-j$, there are $\operatorname{catalan}[j/2-1]$ ways to go from $i-j$ to $i$ without intermediate landings if $j$ is even, and $0$ otherwise, thus we may define↵
↵
$$↵
\operatorname{coef}[j] = \begin{cases}↵
\operatorname{catalan}[j/2-1] & 2 \leq j \leq 2k\text{ is even},\\↵
0 & j\text{ is odd or }j \not\in[2,2k]↵
\end{cases}↵
$$↵
↵
and↵
↵
$$↵
\operatorname{sum}[i] = \operatorname{dp}[0] + \dots + \operatorname{dp}[i].↵
$$↵
↵
Then, we can see the explicit convolution:↵
↵
$$↵
\operatorname{dp}[i] = \sum\limits_{j=0}^{i} \operatorname{sum}[i-j] \cdot \operatorname{coef}[j].↵
$$↵
↵
Let $D(x)$ be the generating function for $\operatorname{dp}$, $C(x)$ the generating function for $\operatorname{coef}$ and $S(x) = \frac{D(x)}{1-x}$ be the generating function for $\operatorname{sum}$. Then the convolution above rewrites as follows:↵
↵
$$↵
D(x) = \frac{D(x)}{1-x} \cdot C(x) + 1,↵
$$↵
↵
thus↵
↵
$$↵
D(x) = \frac{1-x}{1-x-C(x)}.↵
$$↵
↵
Wait, that's an exact solution and can be computed in $O(n \log n)$. Oh no, overkill... Let's go back to $D(x) = S(x) C(x)+1$. As you may see, $C(x)$ is divisible by $x$, and we may rewrite the task as↵
↵
$$↵
D(x) - 1 = x S(x) P(x), ↵
$$↵
↵
where again $P(x)=\frac{C(x)}{x}$ is known in advance and $S(x)$ can be computed from $D(x)-1$ after a new coefficient of it is known.↵
</spoiler>↵
↵
**[Gennady Korotkevich Contest 5 — Bin](https://www.acmicpc.net/problem/18743)**. Find the number of full binary trees with $n$ leaves such that for every vertex with two children, the number of leaves in its left sub-tree doesn’t exceed the number of leaves in its right sub-tree by more than $k$.↵
↵
<spoiler summary="reduction">↵
It's not hard to see that if $T_n$ is the number of such trees, then↵
↵
$$↵
T_n = \sum\limits_{\substack{i+j=n \\ j \leq i + k}} T_i T_j↵
$$↵
↵
with the base case $T_0=0$ and $T_1=1$. One possible way to solve it is to note that↵
↵
$$↵
T_n = \sum\limits_{\substack{i+j=n \\ j < i}} T_i T_j + \sum\limits_{\substack{i+j=n \\ i \leq j \leq i + k}} T_i T_j↵
$$↵
↵
Let $T(x)$ be the generating function of $T_n$ and $D(x)$ be the generating function of↵
↵
$$↵
D_n = T_n - \sum\limits_{\substack{i+j=n \\ i \leq j \leq i + k}} T_i T_j,↵
$$↵
↵
then the recurrence relation is↵
↵
$$↵
D_n = \sum\limits_{\substack{i+j=n \\ j < i}} T_i T_j,↵
$$↵
↵
but in terms of generating functions it rewrites as↵
↵
$$↵
D(x) = \frac{T^2(x) - T(x^2)}{2},↵
$$↵
↵
and to make it a bit more pretty↵
↵
$$↵
2D(x) + T(x^2) = T^2(x).↵
$$↵
↵
Note that $T(x)$ is divisible by $x$ because $T_0=0$, and knowing the $k$-th coefficient of $2D(x)+T(x^2)$ we may as well get the $k$-th coefficient of $T(x)$ from the definition of $D_n$, making CDQ technique applicable.↵
</spoiler>↵
↵
### Solution↵
↵
Okay, how to solve this? Let's recall the convolution formula↵
↵
$$↵
$$↵
↵
↵
Correspondingly, for each $b_j$, values of interest
$$↵
\sum\limits_{i+j=k} a_i b_j = \dots +\sum\limits_{i=l}^m a_i b_{k-i} + \sum\limits_{j=l}^m b_j a_{k-j}↵
$$↵
In the formula above, the first sum only needs $b_j$ for $j$ from $0$ to $\min(m, r-l)$, as values above $m$ will be accounted for elsewhere, and values above $r-l$ do not occur in the sum.↵
↵
Similar holds for the second sum. However, to avoid double-counting $a_i b_j$ when both $i, j \in [l, m)$, we only consider $a_i$ for $i$
↵
- Convolution of $a[l, m)$ with $b[0, \min(m, r-l))$
↵
W
- Convolution of $b[l, m)$ with $a[0, \min(l, r-l))$.↵
↵
Overall, we make two recursive calls and use extra $O(n \log n)$ time to consolidate them, making it
↵
## Generalization↵
↵
Now back to the beginning. The examples above typically expect that the right-hand side is formulated in a way that is kind of similar to convolutions. But there are a lot of functions, for which it's not really possible to do so. Try the following ones in a similar setting (i.e. the coefficients of $f(x)$ are given after the coefficients of $g(x)$ are computed):↵
↵
$$\begin{gather}↵
g(x) =& x \cdot e^{f(x)} \\ \\↵
g(x) =& x \cdot \log \frac{1}{1-f(x)} \\ \\↵
g(x) =& x \cdot \frac{1}{1-f(x)}↵
\end{gather}$$↵
↵
Those are the functions that are quite typical in formal power series (for their interpretation, see [here](https://mirror.codeforces.com/blog/entry/103979)). You may probably rephrase them in a convolution-like manner, so that CDQ is applicable, but you would need to do something ad hoc for each individual function. It doesn't seem very convenient, so it only makes sense to try and find some generic enough approach. What is a generic formulation here?↵
↵
$$↵
g(x) = F(f(x)).↵
$$↵
↵
And you may note that what all these functions $F(\dots)$ have in common is that they're differentiable. Let's use it in a similar way to what we do in Newton's method and rewrite the right hand side in the following way:↵
↵
$$↵
g(x) = F(f_0) + F'(f_0) (f - f_0) + O((f-f_0)^2). ↵
$$↵
↵
This formula generally works for any $f_0$. In particular, let $f_0$ be first $n$ coefficients of $f$, then $(f-f_0)^2$ is divisible by $x^{2n}$. In other words,↵
↵
$$↵
g(x) \equiv F(f_0) + F'(f_0) (f - f_0) \pmod{x^{2n}}.↵
$$↵
↵
In this formula, we still do not know $f(x)$ completely. But what's important is that it is no longer an argument of some generic function $F(\dots)$, so the right-hand side is now a linear function of $f(x)$! This is exactly the formulation for which we learned to apply CDQ convolution above, that is $g(x) = A(x) f(x) + B(x)$, where↵
↵
$$\begin{gather}↵
A(x) =& F'(f_0), \\ \\↵
B(x) =& F(f_0) - f_0 F'(f_0)↵
\end{gather}$$↵
↵
are specific constant polynomials in this context. This sub-problem is solvable in $O(n \log^2 n)$ with the standard CDQ technique, and since it allows us to double the number of known coefficients at each step, the overall running time is also $O(n \log^2 n)$, assuming that we're able to compute $F(\dots)$ and $F'(\dots)$ in $O(n \log^2 n)$ as well.
