感谢 APJifengc 指导 .
看了 xiaoziyao 的复合，大概理解 EI 的思路了，但是似乎细节上有一些问题，在此注记 .
下文「复合」均指右复合 .
前置内容
复合二次分式的内容可以参考参考文献 [2] .
复合 \(ax+b\)
先考虑如何复合 \(x+c\) .
\[\begin{aligned}\mathrm{ans}&=\sum_{i\ge 0}a_i(x+c)^i\\&=\sum_{i\ge 0}a_i\sum_{k=0}^ix^kc^{i-k}\\&=\sum_{k\ge 0}x^k\sum_{i\ge k}a_ic^{i-k}\end{aligned} \]差卷积即可 .
复合 \(ax\) 是平凡的，那么可以简单解决复合一次多项式的问题 .
复合 \(\frac{ax+b}{cx+d}\)
令 \(F^{\sf R}\) 是 \(F\) 的系数翻转，那么显然有 \(F^{\sf R}(x)=x^{\deg F}F(\frac 1x)\) .
取系数 \(\alpha,\beta,\gamma,\delta\) . 翻转系数，复合 \(\alpha x+\beta\) 得到 \((\alpha x+\beta)^nF(\frac1{\alpha x+\beta})\)，再翻转并复合 \(\gamma x+\delta\) 得到 \(\frac{1}{\beta\gamma x+\delta\beta+\alpha}F(\frac{\gamma x+\delta}{\beta\gamma x+\delta\beta+\alpha})\)，解方程即可 .
所以这么算完之后需要一次求逆，求逆带来的后果就是需要截断，所以在后面还有其他复合的时候需要特殊考虑 .
复合 \(ax^3+bx^2+cx+d\)
基本思路
Part 1 规约至复合 \(\bm{x^3+cx}\)
取系数 \(\alpha,\beta,\gamma\)，那么依次复合 \(ax+\gamma,x^3+\beta x,x+\alpha\) 则得到：
\[(ax+\gamma)\circ(x^3+\beta x)\circ(x+\alpha)=ax^3+(3a\alpha)x^2+(3a\alpha^2+a\beta)x+\alpha^3+\alpha^2\beta+\gamma \]那么只需要解出 \(\alpha,\beta,\gamma\)（显然有解）即可把问题规约至复合 \(x^3+cx\) .
Part 2 规约至复合 \(\bm{x^3-3x}\)
断言：解决复合 \(x^3+cx\) 只需要解决任一 \(c_0\neq 0\) 的情况 .
取系数 \(\eta,\theta\)，考察 \((\eta x)\circ(x^3-c_0x)\circ(\theta x)\) 即得（不再展开过程） . 此处无解需要扩域 .
不妨考虑解决 \(x^3-3x\) 的情况 .
Part 3 解决复合 \(\bm{x^3-3x}\)
因为有
\[(x^3-3x)\circ\left(x+\dfrac 1x\right)=x^3+\dfrac1{x^3} \]所以可以得到 \(x^3-3x=(x+\frac 1x)\circ x^3\circ(x+\frac 1x)^{\langle-1\rangle}\) .
注意到：
\[x+\dfrac 1x=(2x)\circ\left(\dfrac{x+1}{x-1}\right)\circ x^2\circ\left(\dfrac{x+1}{x-1}\right) \]那么可以直接得到：
\[x^3-3x=(2x)\circ\left(\dfrac{x+1}{x-1}\right)\circ x^2\circ\left(\dfrac{x+1}{x-1}\right)\circ x^3\circ\left(\dfrac{x+1}{x-1}\right)\circ\sqrt x\circ\left(\dfrac{x+1}{x-1}\right)\circ\left(\dfrac x2\right) \]依次解决即可 .
算法流程
因为之前提到过的复合一次分式的截断问题，这里还需要详细讨论一下 .
下称「变换」为 \(F(x)\to \frac1{(x-1)^{\deg F}}F(\frac{x+1}{x-1})\) .
下面直接描述复合 \(x^3-3x\) 的过程（略去复合 \(2x\) 和 \(\frac x2\) 的部分）
| 编号 | 操作 | 变化 | 次数 |
|---|---|---|---|
| 0 | qwq | \(F(x)\) | \(n\) |
| 1 | 变换 | \((x-1)^nF(\frac{x+1}{x-1})\) | \(n\) |
| 2 | 复合 \(x^2\) | \((x^2-1)^nF(\frac{x^2+1}{x^2-1})\) | \(2n\) |
| 3 | 变换 | \(((\frac{x+1}{x-1})^2-1)^n(x-1)^{2n}F(\frac{x^2+1}{2x})=4^nx^nF(\frac{x^2+1}{2x})\) | \(2n\) |
| 4 | 除 \(4^n\) | \(x^nF(\frac{x^2+1}{2x})\) | \(2n\) |
| 5 | 复合 \(x^3\) | \(x^{3n}F(\frac{x^6+1}{2x^3})\) | \(6n\) |
| 6 | 变换 | \((\frac{x+1}{x-1})^{3n}(x-1)^{6n}F(\frac{x^6-3x^2+1}{x^6-3x^2-1})=(x^2-1)^{3n}F(\frac{x^6-3x^2+1}{x^6-3x^2-1})\) | \(6n\) |
| 7 | 复合 \(\sqrt x\) | \((x-1)^{3n}F(\frac{x^3-3x+1}{x^3-3x-1})\) | \(3n\) |
| 8 | 变换 | \((\frac{x+1}{x-1}-1)^{3n}(x-1)^{3n}F(x^3-3x)=2^{3n}F(x^3-3x)\) | \(3n\) |
| 9 | 除 \(8^n\) | \(F(x^3-3x)\) | \(3n\) |
对于 EI 代码的一些注解：taylor 是平移（复合 \(x+a\)），mobius 是变换 .
参考资料
- [1] 多项式右复合的一些特殊情况 - xiaoziyao
- [2] 任意二次分式均可于 nlogn 时间复合 - 飞雨烟雁
- [3] 关于三次多项式复合的一个注记 - Elegia
- [4] 和 APJifengc 的一些交流