多项式学习笔记
泰勒展开
有 \(F(x)=F(x_{0})+\frac{F'(x_{0})}{1!}(x-x_{0})+\frac{F'(x_{0})}{2!}(x-x_{0})^{2}\cdots +\frac{F^{(n)}(x_{0})}{n!}(x-x_{0})^{n}\)
给定 \(G(x)\) 求解 \(G(F(x))\equiv 0\bmod x^{n}\) 的 \(F(x)\)。
考虑分治：
设 \(f_{0}(x)\) 是 $G(F(x))\equiv 0\bmod x^{\lceil \frac{n}{2}\rceil} $。
注意到 \(F(x)\) 与 \(f_{0}(x)\) 的前 \(\lceil \frac{n}{2}\rceil\) 位是相同的，于是可以对 \(G(F(x))\) 在 \(f_{0}(x)\) 处展开，那么就有：
\[\sum_{i=0}^{\inf} \frac{g^{(i)}(f_{0}(x))}{i!}(f(x)-f_{0}(x))^{i}\equiv 0 \bmod x^{n} \]然后因为当 \(i\ge 2\) 时，\((f(x)-f_{0}(x))^{i} \bmod x^{n}\equiv 0\)。所以只需要考虑 \(i=0,1\) 的情况，然后可以得到 \(f(x)\equiv f(x_{0})-\frac{g(f(x))}{g'(f(x))}\)。这个式子下面将会起到关键的作用。
多项式的基本运算
乘法逆：
给定 \(g(x)\)，求 \(f(x)g(x)\equiv 0\bmod x^{n}\)。
根据泰勒展开，设 \(h(f(x))=\frac{1}{f(x)}-g(x)\equiv 0\)，则有：
\[f(x)=f_{0}(x)-\frac{h(f(x))}{h'(f(x))}=f_{0}(x)-\frac{\frac{1}{f(x)}-g(x)}{\frac{1}{-f^{2}_{0}(x)}} \]则有 \(f(x)=2f_{0}(x)-f_{0}^{2}(x)g(x)\)。暴力 NTT 时间复杂度 \(O(n\log n)\)。
开根：
给定 \(g(x)\)，求 \(f(x)\) 使得 \(f^2(x)\equiv g(x) \bmod x^{n}\)。
同样泰勒展开，设 \(h(f(x))=f^2(x)-g(x)\equiv 0\)，则有
\[f(x)=f_{0}(x)-\frac{h(f(x))}{h'(f(x))}=f_{0}(x)-\frac{f^2(x)-g(x)}{2f(x)} \]从而转化成了多项式求逆问题，时间复杂度还是 \(O(n\log n)\) 的，但是常数巨大。
代余除法：
给定 \(n\) 次多项式 \(F(x)\)，\(m\) 次多项式 \(G(x)\)，求 \(Q(x),R(x)\) 使得 \(F(x)=Q(x)\times G(x)+R(x)\)。
给出一个推论：\(F^{R}(x)=x^{deg(F(x))}F(\frac{1}{x})\)，\(F^{R}(x)\) 表示系数翻转的多项式，这个模拟一下就可以证明。
那么对于这个问题，令 \(x'=\frac{1}{x}\)，那么有 \(F^{R}(x')=Q^{R}(x')\times G^{R}(x')+x^{n-deg(R(x))}R^{R}(x)\)，因为 \(deg(R(x))\) 显然是 \(<m\) 的，而 \(G^{R}(x')\) 的次数一定 \(\le n-m+1\)，所以显然可以放在模 \(x^{n-m+1}\) 的意义下来做，此时后面的 \(R(x)\) 项就没有贡献，直接多项式求逆即可。
多项式求 \(\ln\)：
给定 \(F(x)\)， 求 \(G(x)\equiv \ln F(x)\)。
\(\ln\) 的求导形式非常好，考虑求导得： \(G'(x)\equiv \frac{F'(x)}{F(x)}\)。注意到对于复合函数求导需要对内外的函数均求导，所以是 \(\frac{F'(x)}{F(x)}\)。然后就是多项式求逆。
多项式求 exp：
给定 \(G(x)\)，求 \(G(x)\equiv e^{G(x)}\)。
考虑取 $\ln $，即 \(\ln F(x)\equiv G(x)\)，然后泰勒展开即可得到 \(F(x)=f_{0}(x)(1-\ln f_{0}(x)+G(x))\)。
递归求解，过程和求逆类似。
快速幂：
给定 \(A(x),k\)，求 \(B(x)\equiv A(x)^{k}\bmod x_{n}\)。
等式两边均取 ln，得 \(\ln B(x)\equiv k\ln A(x)\)，转为求 exp。
标签：frac,ln,多项式,bmod,笔记,学习,给定,equiv From： https://www.cnblogs.com/OIshima/p/18005174