In Elegia's blog [How to composite (some) polynomials faster](https://codeforces.me/blog/entry/126124), we know how to compose some special power series in $\mathcal O(n\log n)$ time, especially for the quadratic rational fraction $(ax^2+bx+c)/(dx^2+ex+f)$ and the cubic polynomial $ax^3+bx^2+cx+d$. In this blog I will show how to use this method to calculate $\prod_{i=1}^n(x-g(i))$ in $\mathcal O(n\log n)$ time, where $g(x)$ is a quadratic rational fraction, written as $(ax^2+bx+c)/(dx^2+ex+f)$.↵
↵
### Basic Knowledge↵
↵
Let's review how to calculate $f_n(x):=\prod_{i=1}^n(x-i)$ in $\mathcal O(n\log n)$ time. We solve this problem by recursion. ↵
↵
If $n$ is even, assuming we have already computed $f_{n/2}$, then $f_n(x)=f_{n/2}(x)\cdot f_{n/2}(x-n/2)$, which could be calculated in $\mathcal O(n\log n)$ time.↵
↵
If $n$ is odd, assuming we have already computed $f_{n-1}$, then $f_n(x)=f_{n-1}(x)\cdot (x-n)$, which could be calculated in $\mathcal O(n)$ time.↵
↵
Hence, we know that the time complexity of this algorithm is $T(n)=T(n/2)+\mathcal O(n\log n)$. According to Master Theorem, $T(n)=\mathcal O(n\log n)$.↵
↵
Also, this is the classic solution for calculating (signed) Stirling numbers of the first kind ${n\brack k}, 1\le k\le n$ in $\mathcal O(n\log n)$ time.↵
↵
### Main Tricks↵
↵
For convenience, we may assume that $g(i)\neq0,\forall 1\le i\le n$.↵
↵
From the above, we know how to find $\prod_{i=1}^n (x-g(i))$ when $g(x)=x$. At the same time, we know that we can use $ax+b,x^2,x^{-1}$ to construct a composition chain for any quadratic rational fractions. For example, ↵
↵
$$\frac{x+1}{x^2}=(x-1/4)\circ x^2\circ (x+1/2)\circ x^{-1}.$$↵
↵
Therefore, it remains to show that if we can calculate $\prod_{i=1}^n (x-g(i))$ in $\mathcal O(n\log n)$ time, then so are $\prod_{i=1}^n [x-(ag(i)+b)],\prod_{i=1}^n (x-g(i)^2),\prod_{i=1}^n (x-1/g(i))$. Here, we regard $g(x)$ as some unknown function, not necessarily the quadratic rational fractions.↵
↵
Let $G(x)=\prod_{i=1}^n (x-g(i))$.↵
↵
For the first one, notice that ↵
↵
$$\prod_{i=1}^n [x-(ag(i)+b)]=a^nG\left(\frac{x-b}{a}\right),$$↵
↵
so we are done.↵
↵
For the second one, notice that↵
↵
$$\prod_{i=1}^n (x-g(i)^2)=[(-1)^nG(x)G(-x)]\circ x^{1/2},$$↵
↵
so we are done.↵
↵
For the third one, notice that↵
↵
$$\prod_{i=1}^n(x-1/g(i))=\frac{1}{G(0)}\cdot x^nG(1/x),$$↵
↵
so we are done.↵
↵
Quite easy!↵
↵
As a reminder, $\prod_{i=1}^n (x-g(i)^k)$ could also be calculated in $\mathcal O(n\log n)$ time (omit $k$ in time complexity), if we acknowledge the existence of $k$-th primitive root.↵
↵
### Some Application↵
↵
Using the ln-exp tricks, we can also calculate $\sum_{i=1}^n h(g(i)x)\bmod x^n$, where $g$ is quadratic rational fraction, $h$ is any power series. The key is to find out $\sum_{i=1}^n g(i)^j,1\le j\le n$, which is $-j[x^j]\log \prod_{i=1}^n(1-g(i)x)$. Therefore we are done!↵
↵
### Further Discussion↵
↵
Compared to the basic element in the composition for cubic polynomial, we found that we didn't discuss how to calculate $\prod_{i=1}^n(x-g(i)^{1/2})$ yet! The main obstacle is that though it's easy to find $F(x)$ in the function equation $G(x)G(-x)=F(x^2)$ when $G(x)$ is known, we do not know how to solve $G(x)$ when $F(x)$ is given. Therefore, for any cubic polynomial $g(x)$, I don't know how to calculate $\prod_{i=1}^n(x-g(i))$ in $\mathcal O(n\log n)$ time.↵
↵
Unfortunately!↵
↵
↵
### Basic Knowledge↵
↵
Let's review how to calculate $f_n(x):=\prod_{i=1}^n(x-i)$ in $\mathcal O(n\log n)$ time. We solve this problem by recursion. ↵
↵
If $n$ is even, assuming we have already computed $f_{n/2}$, then $f_n(x)=f_{n/2}(x)\cdot f_{n/2}(x-n/2)$, which could be calculated in $\mathcal O(n\log n)$ time.↵
↵
If $n$ is odd, assuming we have already computed $f_{n-1}$, then $f_n(x)=f_{n-1}(x)\cdot (x-n)$, which could be calculated in $\mathcal O(n)$ time.↵
↵
Hence, we know that the time complexity of this algorithm is $T(n)=T(n/2)+\mathcal O(n\log n)$. According to Master Theorem, $T(n)=\mathcal O(n\log n)$.↵
↵
Also, this is the classic solution for calculating (signed) Stirling numbers of the first kind ${n\brack k}, 1\le k\le n$ in $\mathcal O(n\log n)$ time.↵
↵
### Main Tricks↵
↵
For convenience, we may assume that $g(i)\neq0,\forall 1\le i\le n$.↵
↵
From the above, we know how to find $\prod_{i=1}^n (x-g(i))$ when $g(x)=x$. At the same time, we know that we can use $ax+b,x^2,x^{-1}$ to construct a composition chain for any quadratic rational fractions. For example, ↵
↵
$$\frac{x+1}{x^2}=(x-1/4)\circ x^2\circ (x+1/2)\circ x^{-1}.$$↵
↵
Therefore, it remains to show that if we can calculate $\prod_{i=1}^n (x-g(i))$ in $\mathcal O(n\log n)$ time, then so are $\prod_{i=1}^n [x-(ag(i)+b)],\prod_{i=1}^n (x-g(i)^2),\prod_{i=1}^n (x-1/g(i))$. Here, we regard $g(x)$ as some unknown function, not necessarily the quadratic rational fractions.↵
↵
Let $G(x)=\prod_{i=1}^n (x-g(i))$.↵
↵
For the first one, notice that ↵
↵
$$\prod_{i=1}^n [x-(ag(i)+b)]=a^nG\left(\frac{x-b}{a}\right),$$↵
↵
so we are done.↵
↵
For the second one, notice that↵
↵
$$\prod_{i=1}^n (x-g(i)^2)=[(-1)^nG(x)G(-x)]\circ x^{1/2},$$↵
↵
so we are done.↵
↵
For the third one, notice that↵
↵
$$\prod_{i=1}^n(x-1/g(i))=\frac{1}{G(0)}\cdot x^nG(1/x),$$↵
↵
so we are done.↵
↵
Quite easy!↵
↵
As a reminder, $\prod_{i=1}^n (x-g(i)^k)$ could also be calculated in $\mathcal O(n\log n)$ time (omit $k$ in time complexity), if we acknowledge the existence of $k$-th primitive root.↵
↵
### Some Application↵
↵
Using the ln-exp tricks, we can also calculate $\sum_{i=1}^n h(g(i)x)\bmod x^n$, where $g$ is quadratic rational fraction, $h$ is any power series. The key is to find out $\sum_{i=1}^n g(i)^j,1\le j\le n$, which is $-j[x^j]\log \prod_{i=1}^n(1-g(i)x)$. Therefore we are done!↵
↵
### Further Discussion↵
↵
Compared to the basic element in the composition for cubic polynomial, we found that we didn't discuss how to calculate $\prod_{i=1}^n(x-g(i)^{1/2})$ yet! The main obstacle is that though it's easy to find $F(x)$ in the function equation $G(x)G(-x)=F(x^2)$ when $G(x)$ is known, we do not know how to solve $G(x)$ when $F(x)$ is given. Therefore, for any cubic polynomial $g(x)$, I don't know how to calculate $\prod_{i=1}^n(x-g(i))$ in $\mathcal O(n\log n)$ time.↵
↵
Unfortunately!↵
↵
