多项式学习笔记
泰勒展开
有 \(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