概述

设 $\mathbb{A}$ 是一个交换环， $f,g\in \mathbb{A}[x]$ 满足次数小于 $n$ ，需要快速求出 $f(g(x))\bmod x^n$ 。

设 $M(n)$ 是两个次数小于 $n$ 的 $\mathbb{A}[x]$ 中的元素相乘所需的时间复杂度。

1978：Brent-Kung 算法。 $O(M(n)\sqrt{n\log n})$

2008: Kedlaya ,Umans 提出的算法。

只能在 $F_q$ 下面做, $\widetilde{O}(n2^{O(\sqrt{\log n\log \log n})}\log q)$

2023: Neiger,Salvy 等人提出的算法。 $O(n^{1.43})$

2024：Yasunori Kinoshita 和 Baitian Li 在 FOCS 2024 提出了一个简单、高效的算法。

Bostan-Mori,Power Projection

对于项数小于 $n$ 的 $f,g\in A[x]$ ,求 $[x^m]\frac{f(x)}{g(x)}$ 。

$\frac{f(x)}{g(x)}=\frac{f(x)g(-x)}{g(x)g(-x)}$

设 $f(x)g(-x)=a_0 x^{0}+a_1 x^{1}+\dots $。提取出其奇数项和偶数项，记 $f_0(x)=a_0x^0+a_2x^1+a_4x^2+\dots,f_1(x)=a_1x^0+a_3x^1+a_5x^2+\dots$ 。

$g(x)g(-x)$ 是偶函数，令 $p(x)=\sum x^i[x^{2i}]g(x)g(-x)$ 。

则 $[x^m]\frac{f(x)}{g(x)}=[x^{\lfloor{\frac{m}{2}}\rfloor}]\frac{f_{m\bmod 2}(x)}{p(x)}$

算法复杂度 $O(M(n)\log m)$ 。

现在我们解决以下问题：给定项数小于 $n$ 的 $f\in \mathbb{A}[x]$ ,求出 $[x^n]f^0(x),[x^n]f^1(x),\dots,[x^n]f^n(x)$ 。

等价于求 $[x^n]\frac{1}{1-yf(x)}$ 。采用类似的思路。

可以看成是两个二元多项式 $f(x,y),g(x,y)\in \mathbb{A}[x,y]$ ，求 $[x^n]\frac{f(x,y)}{g(x,y)}$ 。

设 $f_0(x,y),f_1(x,y)$ 是 $f(x,y)g(-x,y)$ 关于 $x$ 提取偶数项，奇数项的结果。

设 $p(x,y)$ 是 $g(x,y)g(-x,y)$ 关于 $x$ 提取偶数项后的结果。

则 $[x^n]\frac{f(x,y)}{g(x,y)}=[x^{\lfloor{\frac{n}{2}}\rfloor}]\frac{f_{n\bmod 2}(x,y)}{p(x,y)}$ 。

递归到 $[x^0]\frac{f(x,y)}{g(x,y)}$ 的时候直接求 $\frac{[x^0]f(x,y)}{[x^0]g(x,y)}$ 就好了。

分析一下上述算法的时间复杂度。

递归 $i$ 轮后 $f(x,y),g(x,y)$ 中 $x$ 的次数不超过 $\frac{n}{2^i}$ ， $y$ 的次数不超过 $2^i$ 。

递归 $\log n$ 轮，复杂度 $O(M(n)\log n)$ 。

基于转置原理的方法

转置原理：对于一个 $n×n$ 的矩阵 $A$ 。

若存在一个算法可以对任意长度为 $n$ 的列向量 $b$ 计算出 $Ab$ 。

那么一定存在一个算法能够以相同的效率计算 $A^Tb$ 。

回顾我们的问题，设矩阵 $A^T$ 满足 $A_{i,j}=[x^i]g^j(x)$ ， $f$ 形成的列向量为 $b$ 。则需要计算 $A^Tb$ 。

只需要思考 $Ab$ 的求法即可，即计算 $a_j=\sum b_iA_{i,j}=\sum b_i[x^i]g^j(x)$ 。

设 $h(x)=\sum b_ix^{n-i}$ ，则 $a_j=[x^ny^j]\frac{h(x)}{1-yg(x)}$ 。

使用 Bostan-Mori 即可。

不需要转置原理的方法

设 $P(y)=y^nf(y^{-1}),Q(x,y)=1-yg(x)$ ，则：

$f(g(x))=\sum\limits_{i=0}^n ([y^i]f(y))g(x)^i= [y^n]y^nf(y^{-1})\frac{1}{1-yg(x)}=[y^n]\frac{P(y)}{Q(x,y)}$

记 $\mathcal{F} _{l,r}(Q(x,y))=\sum\limits_{i=l}^{r-1} y^{i-l}[y^i]Q(x,y)$ ，则我们希望求出 $\mathcal{F}_{n,n+1}(\frac{P(y)}{Q(x,y)})\bmod x^n$ 。

思考 $\mathcal{F}_{l,r}(\frac{P(y)}{Q(x,y)})\bmod x^n$ 的求法。

$n=1$ 时，答案即 $\mathcal{F}_{l,r}(\frac{P(y)}{Q(0,y)})$ 。

$n>1$ 时，考虑

$\mathcal{F}_{l,r}(\frac{P(y)}{Q(x,y)})\bmod x^n=\mathcal{F}_{l,r}(\frac{P(y)Q(-x,y)}{Q(x,y)Q(-x,y)\bmod x^n\bmod y^r})\bmod x^n=\mathcal{F}_{l,r}(\frac{P(y)}{V(x^2,y)}Q(-x,y))\bmod x^n:=u$

其中 $V(x^2,y)=Q(x,y)Q(-x,y)\bmod x^n\bmod y^r$ 。

记 $e=\max(0,l-deg_y Q(x,y))$ 。

$u=\mathcal{F}_{l,r}\left(y^e\mathcal{F}_{e,r}(\frac{P(y)}{V(x^2,y)})Q(-x,y)\right)\bmod x^n=\mathcal{F}_{l-e,r-e}\left(\mathcal{F}_{e,r}(\frac{P(y)}{V(x^2,y)})Q(-x,y)\right)\bmod x^n=\mathcal{F}_{l-e,r-e}\left(\mathcal{F}_{e,r}(\frac{P(y)}{V(z,y)})\bmod z^{\lceil{\frac{n}{2}}\rceil}|_{z=x^2}Q(-x,y)\right)\bmod x^n$

递归计算 $\mathcal{F}_{e,r}(\frac{P(y)}{V(x,y)})\bmod x^{\lceil{\frac{n}{2}}\rceil}$ 即可。

可以发现递归至第 $i+1$ 轮时， $deg_xQ(x,y)\le \frac{n}{2^i},deg_yQ(x,y)\le 2^i,r-l\le 2^i$ 。

复杂度 $O(M(n)\log n)$ 。

$n=1$ 时不需要对多项式进行求逆。

设初始的分母为 $Q_0(x,y)$ 。

考虑递归 $d$ 轮后 $Q_d(x,y)=(Q_0(x,y)Q_0(-x,y))^{2^{d-1}}$ ，则 $Q_d(0,y)=Q_0(0,y)^{2^d}$ 。

代入 $Q_0(0,y)=1-yg(0)$ ，得到 $\frac{1}{(1-yg(0))^{2^d}}=\sum\limits_{i\geq 0}(yg(0))^i\tbinom{2^d-1+i}{i}$ 。

这就说明了为什么对任何交换环 $\mathbb{A}$ ，这个算法都可以计算 $f,g\in \mathbb{A}[x]$ 时的 $f(g(x))$ 。

总结

两个做法都是将问题转化为求二元分式的某项值，然后通过类似 Bostan-Mori 的算法求解。

但又存在一定区别：一个需要计算 $[x^n]\frac{h(x)}{1-yg(x)}$ ，一个需要计算 $[y^n]\frac{h(y)}{1-yg(x)}$ ，所以具体步骤存在很多不同。