526互联

关于 EI 的三次多项式复合的一些注解

发布时间 2023-10-15 09:30:26作者: Jijidawang

感谢 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 是变换 .

参考资料