前言
如果完全不会求导和积分，以及泰勒展开，这里有一个实用性很强的教程 3blue1brown - 微积分的本质。
多项式牛顿迭代
给定函数 \(G(x)\)，求多项式 \(F(x)\) 使得 \(G(F(x)) \equiv 0 \pmod {x^n}\)。
当 \(n=1\) 时，可以单独求出 \([x_0]F(x)\)（大部分问题中该解易求）。
考虑已经得到模 \(x^{\left \lceil \frac n2 \right \rceil}\) 意义下的解，如何求出模 \(x^n\) 意义下的解。
将 \(G(F(x))\) 在 \(F_0(x)\) 处泰勒展开，有
\[\sum \limits_{i=0}^{+\infty} \dfrac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i \equiv 0 \pmod {x^n} \]其中，\(G^{(i)}\) 表示 \(G\) 的 \(i\) 阶导函数。
而 \(F(x)-F_0(x)\) 的最高次数非零项的次数肯定大于 \(\left \lceil \dfrac{n}{2} \right \rceil\)，所有 \(i>1\) 的项在模 \(x^n\) 意义下都会变成 \(0\)。
于是，上式等价于
\[G(F_0(x)) + G'(F_0(x))(F(x)-F_0(x)) \equiv 0 \pmod {x^n} \]整理得
\[F(x) \equiv F_0(x) - \dfrac{G(F_0(x))}{G'(F_0(x))} \pmod {x^n} \]应用 1 多项式求逆
给定 \(H(x)\) 求 \(F(x)\) 使得 \(F(x)H(x) \equiv 1 \pmod {x^n}\)。（使用 \(H\) 是为了和多项式牛顿迭代中的 \(G\) 区分）
有方程
\[G(F(x)) \equiv \dfrac{1}{F(x)} - H(x) \equiv 0 \pmod {x^n} \]牛顿迭代，得
\[F(x) \equiv F_0(x) - \dfrac{G(F_0(x))}{G'(F_0(x))} \pmod{x^n} \]\[F(x) \equiv F_0(x) - \dfrac{\frac{1}{F_0(x)}-H(x)}{-\frac{1}{F_0^2(x)}} \pmod{x^n} \]\[F(x) \equiv 2F_0(x)-F_0^2(x)H(x) \pmod{x^n} \]\[F(x) \equiv F_0(x)(2-F_0(x)H(x)) \pmod{x^n} \]递归求解即可。边界：\(n=0\) 时需要求解该项系数的乘法逆元。
应用 2 多项式开根
给定 \(H(x)\) 求 \(F(x)\) 使得 \(F^2(x) \equiv 1 \pmod {x^n}\)。
使用牛顿迭代，有方程
\[G(F(x)) \equiv F^2(x)-H(x) \equiv 0 \pmod {x^n} \]\[F(x) \equiv F_0(x) - \dfrac{F_0^2(x)-H(x)}{2F_0(x)} \pmod{x^n} \]\[F(x) \equiv F_0(x) +\dfrac{H(x)-F_0^2(x)}{2F_0(x)} \pmod{x^n} \]\[F(x) \equiv \dfrac{H(x)+F_0^2(x)}{2F_0(x)} \pmod{x^n} \]\[F(x) \equiv \dfrac 12\left(\dfrac{H(x)}{F_0(x)}+F_0(x) \right)\pmod{x^n} \]每层求逆即可，复杂度不变。注意这个时候 NTT 要在模 \(x^{2n}\) 意义下做，因为 \(H(x),\dfrac{1}{F_0(x)}\) 在模 \(x^n\) 意义下都是 \(n-1\) 次多项式。
应用 3 多项式 exp
给定 \(H(x)\) 求 \(F(x)\) 使得 \(\exp H(x) \equiv F(x) \pmod {x^n}\)。
使用牛顿迭代，有方程
\[G(F(x)) \equiv \ln F(x) - H(x) \equiv 0 \pmod {x^n} \]\[F(x) \equiv F_0(x) - \dfrac{\ln F_0(x) - H(x)}{\frac{1}{F_0(x)}} \pmod {x^n} \]\[F(x) \equiv F_0(x)(1-\ln F_0(x) + H(x))\pmod {x^n} \]\(n=0\) 的时候要检查 \([x^0]H(x)\) 是不是等于 \(0\)，不是 \(0\) 就寄了，这种情况下 \(e^x\) 是个超越数，不能在模意义下被表示出来。同时注意，NTT 要在模 \(x^{2n}\) 意义下做。
标签：迭代,pmod,多项式,瞎口,牛顿,dfrac,equiv From： https://www.cnblogs.com/liuzongxin/p/16647207.html