多项式牛顿迭代
解决的问题：求一个[多项式函数]（？）\(G\)，使得 \(F(G) \equiv 0 \pmod {x ^ n}\)。
（听 XK 提到 泛函分析）
\[G_{k+1} \equiv G_k - \frac { F(G_k) } { F'(G_k) } \pmod {x ^ { 2 ^ { k + 1 } }} \]求导时把 \(G\) 当成未知数，不要对 \(G\) 求导。
倍增。
加法
每一项对应加。
时间 \(O(n)\)。
乘法
NTT。
时间 \(O(n \log n)\)。
求导
对每一项分别求导。
由
\[(x ^ n)' = n x ^ {n - 1} \]得
\[f' _ i = (i + 1) f _ { i + 1 } \]时间 \(O(n)\)。
积分
就是求导反过来。
\[f _ i = \frac { f' _ { i - 1 } } { i } \]时间 \(O(n)\)。
求逆
把式子变成 \(\ldots \equiv 0\) 的形式。设左边那一堆为 \(H(G)\)。（\(G\) 是要求的多项式）
要求 \(H(G) = 0\)，牛顿迭代求 \(G\) 即可。
初值（\(g_0\)）等于 \(f_0\) [在模意义下]（？）的乘法逆元。
时间 \(O(n \log n)\)。
[开平方根]（？）
牛顿迭代（类似求逆）。
初值可能要用二次剩余。
\(\ln\) 和 \(\exp\) 互为逆运算。
ln
\[\ln G(x) = F(x) \]给 \(F\)，求 \(G\)。
推式子要用：
\[\ln ' ( x ) = \frac { 1 } { x } \]推式子：对两边求导，再把两边都积分回去。
做：对于左边，求导、求逆 -> 相乘 -> 积分。
初值 \(\ln 1 = 0\)。（不能有其他的吗？）
时间 \(O(n \log n)\)。
exp
先对两边求 \(\ln\)。再用牛顿迭代（类似求逆）做，要用多项式 \(\ln\)。
时间 \(O(n \log n)\)。
除法、取余
\[F(x) = G(x) H(x) + R(x) \]给 \(F, G\)，求 \(H, R\)。
\(F\) 的次数是 \(n\)，\(G\) 的次数是 \(m\)。那么 \(H\) 的次数就是 \((n - m)\)，而 \(R\) 的次数是 \(m - 1\)。
等式两边把 \(x\) 换成 \(x ^ { - 1 }\) 后同乘 \(x ^ n\)，得到系数翻转后的多项式。\(\pmod {x ^ { n - m + 1 }}\) 把 \(R\) 变成的那个多项式变成 \(0\)，而且这样不会使 \(H\) 有损失，因为系数翻转后的 \(H\) 的次数 \((n - m)\) 小于 \((n - m + 1)\)。于是直接用多项式求逆和多项式乘法求出系数翻转后的 \(H\)。然后把系数翻转回来求出真正的 \(H\)，再利用它求 \(G\)（多项式乘法、多项式减法）即可。
时间 \(O(n \log n)\)。
原理的关键在于我们可以用 \(\pmod {x ^ \ldots}\) 来去掉次数较高的项。但是这里 \(R\) 的次数较小，所以我们把系数翻转再用 \(\pmod {x ^ \ldots}\) 来消除 \(R\) 变成的多项式的影响。（从 https://zhuanlan.zhihu.com/p/678382384 和 https://www.cnblogs.com/blog-Dr-J/p/10487228.html 学到这一点）
2024.8.10
标签：求逆,log,简略,ln,多项式,全家,pmod,求导 From： https://www.cnblogs.com/huangkxQwQ/p/18352739