省选-数学-多项式全家桶 · Zhl2010 第二博客

泰勒展开

G(t) \approx G(t_0) + G'(t_0)\cdot (t-t_0)

$t_0$ 是已知基准点， $G'(t_0)$ 为一阶导数。

G(t) = \sum_{i=0}^{\infty} \frac{G^{(i)}(t_0)}{i!}\,(t-t_0)^i

$G^{(i)}$ 表示 $i$ 阶导数，本题高阶项全部舍去。

将实数变量替换为多项式： $t\to F(x),\ t_0\to F_0(x)$

G\big(F(x)\big) \approx G\big(F_0(x)\big) + G'\big(F_0(x)\big)\cdot \big(F(x)-F_0(x)\big)

令 $D(x) = F(x)-F_0(x)$ ，由

F_0(x) \equiv F(x) \pmod{x^{\lceil \frac{n}{2} \rceil}}

可知 $D(x)$ 最低次为 $x^{\lceil \frac{n}{2} \rceil}$ ，因此 $D(x)^2$ 次数 $\ge n$ 。根据多项式模规则：

D(x)^2 \equiv 0 \pmod{x^n}

二次及更高次幂均为 $0$ ，最终模运算下等式：

G\big(F(x)\big) \equiv G\big(F_0(x)\big) + G'\big(F_0(x)\big)\cdot D(x) \pmod{x^n}

也就是泰勒展开的更高次项都变成 $0$ 了。

结合方程 $G\big(F(x)\big) \equiv 0 \pmod{x^n}$ ，代入并整理：

0 = G(F_0) + G'(F_0)\cdot \big(F-F_0\big)

F = F_0 - \frac{G(F_0)}{G'(F_0)}

也就是牛顿迭代法的式子了：

F_1(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}

已知 $F(x)$ ，要求出 $G(x) * F(x) \equiv 1 \pmod{x^n}$ ，对 $998244353$ 取模。

F(x) - \frac{1}{G(x)} \equiv 0 \pmod{x^n}

用牛顿迭代法计算，我们定义 $H(t)$ ：

H(t)=F(x)-\frac{1}{t}

可以发现：

H(G(x)) \equiv 0 \pmod{x^n}

然后带入牛顿迭代公式：

G_1(x)=G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}

然后换掉 $H$ ：

G_1(x)=G_0(x) - \frac{F(x)-\frac{1}{G_0(x)}}{\frac{1}{G_0(x)^2}}

G_1(x)=G_0(x)(2-G_0(x)F(x))

求 $G(x)$ 使得 $G(x)\equiv \ln F(x)$ 。

令 $f(x)=\ln(x)$ ：

$G(x)\equiv f(F(x))\ (\text{mod}\ \ x^n)$

同时求导。 $f(F(x))$ 是个复合函数，复合函数求导公式为 $f(g(x))'=f'(g(x))g'(x)$ ：

$G'(x)=f'(F(x))F'(x)\ (\text{mod}\ \ x^n)$

由 $\ln'(x)={1\over x}$ ：

$G'(x)={F'(x)\over F(x)}\ (\text{mod}\ \ x^n)$

然后我们只需要对 $F$ 求逆，然后计算乘法，然后再积分起来就行了。

{G(x) = \int \frac{F'(x)}{F(x)} \mathrm{d}x}

$G(x)\equiv e^{A(x)}\pmod{x^n}$

$\ln G(x)-A(x)\equiv 0\pmod{x^n}$

迭代函数：

$F(G(x))=\ln G(x) - A(x)$

带入牛顿迭代法的公式中：

G(x)&\equiv G_0(x)-\frac{\ln G_0(x)-A(x)}{\frac 1 {G_0(x)}}\pmod{x^n} \\ &\equiv G_0(x)-G_0(\ln G_0(x)-A(x))\pmod{x^n} \\ &\equiv G_0(x)(1-\ln G_0(x)+A(x))\pmod{x^n} \end{aligned}$$ 注意：这个 $1$ 只在 $0$ 这个位置需要加上，因为这个 $1$ 相当于是给全局加的。 ### P5245 【模板】多项式快速幂 [P5245 【模板】多项式快速幂](https://www.luogu.com.cn/problem/P5245)。 $$a^b=e^{b\ln a}$$ 求出 $k\ln A(x)$，再$\exp$回来。 --- 更好写的方法：

e^{k\ln A(x)} \equiv e^{(k\bmod p)\ln A(x)} \equiv A(x)^{k\bmod p} \pmod{x^n}

因为这是多项式模，还需要 $\mod x^n$，所以上面的式子是对的。 ---- ### P5277 【模板】多项式开根（加强版） [P5277 【模板】多项式开根（加强版）](https://www.luogu.com.cn/problem/P5277)。 不保证 $F(0)=1 $了，$exp$ 中 $F_0$ 也就不一定是 $0$ 了不可以直接求了。 尝试把 $F(x)$ 的每一项都除以 $F(0)$。 $$F(x)^k=\left(\frac{F(x)}{F(0)} \right)^kF(0)^k$$ 但是可以 $F(0)=0$。 所以我们要找出最小的 $t$，满足 $F(x)$ 的 $t$ 次项不为 $0$。 $$F(x)^k=\left(\frac{F(x)}{x^t} \right)^kx^{tk}$$ ### P5205 【模板】多项式开根 [P5205 【模板】多项式开根](https://www.luogu.com.cn/problem/P5205)。 貌似这个推导方法更加神奇： ::::info[推导] 令 $m=\lceil \dfrac{n}{2} \rceil$。 $$H^2(x)\equiv F(x)\pmod{x^{m}}$$ $$G(x)\equiv H(x)\pmod{x^{m}}$$ $$G(x)-H(x)\equiv 0\pmod{x^{m}}$$ $$(G(x)-H(x))^2\equiv 0\pmod{x^{n}}$$ $$G^2(x)-2H(x)*G(x)+H^2(x)\equiv 0\pmod{x^n}$$ $$F(x)-2H(x)*G(x)+H^2(x)\equiv 0\pmod{x^n}$$ $$G(x)=\frac{F(x)+H^2(x)}{2H(x)}$$ :::: 注意不要两个函数用同一个全局变量这是第二次了。 ### P4389 付公主的背包 [P4389 付公主的背包](https://www.luogu.com.cn/problem/P4389)。

G(x) = \prod_{V} \left(\frac{1}{1-x^V}\right)^{\text{cnt}_V}

\ln G(x) = -\sum_V \text{cnt}_V \ln(1-x^V)

由于：

\ln(1-x^V) = -\sum_{k\ge 1}\frac{x^{Vk}}{k}

所以：

\ln G(x) = \sum_V \text{cnt}V \sum{k\ge 1} \frac{x^{Vk}}{k}

这个式子我们就可以快速求了。