一些多项式常用操作的公式推导

标签：推导 pmod dfrac times 公式 多项式 aligned equiv

怕我以后忘记了看不懂自己的板子（（（

牛顿迭代

用于求解函数零点的近似值。

设函数 \(f(x)\) 的零点近似值为 \(x_0\)，过点 \((x_0,f(x_0))\) 作 \(f(x)\) 的切线，切线与 \(x\) 轴交点的横坐标即为新的近似值。

切线解析式为 \(y=f'(x_0)(x-x_0)+f(x_0)\)，当 \(y=0\) 时 \(x=x_0-\dfrac{f(x_0)}{f'(x_0)}\)。

同理，若要求满足 \(G(F(x))=0\) 的多项式 \(F(x)\)，则 \(F(x)=F_0(x)-\dfrac{G(F_0(x))}{G'(F_0(x))}\)，每迭代一次精度翻倍。

---

P4238 多项式求逆

\[\begin{aligned} A(x)\times F(x)&\equiv 1\pmod{x^n}\\ \\ \dfrac{1}{F(x)}&\equiv A(x)\pmod {x^n}\\ \\ \dfrac{1}{F(x)}-A(x)&\equiv 0\pmod {x^n}\\ \end{aligned}\]

令 \(G(F(x))=\dfrac{1}{F(x)}-A(x)\)，求 \(\dfrac{1}{A(x)}\) 即为求 \(G(F(x))\) 的零点。

代入牛顿迭代的式子：

\[F(x)=F_0(x)-\dfrac{\dfrac{1}{F(x)}-A(x)}{G'(F_0(x))} \]

将 \(G(F(x))\) 中的 \(F(x)\) 看作变量，\(A(x)\) 看作常数，可得 \(G'F(x)=-\dfrac{1}{F(x)^2}\)，代入得

\[\begin{aligned} F(x)&=F_0(x)+(\dfrac{1}{F_0(x)}-A(x))\times F_0(x)^2\\ \\ F(x)&=2F_0(x)-A(x)\times F_0(x)^2\\ \end{aligned}\]

初始时 \(F_0(x)=\dfrac{1}{A(0)}\)。

---

P4512 多项式除法

对于任意 \(n\) 次多项式 \(A(x)\)，设 \(A_r(x)=\displaystyle\sum_{i=0}^n[x^{n-i}]A(x)x^i\)。

\(\displaystyle A_r(x)=\sum_{i=0}^n[x^{n-i}]A(x)(\dfrac{1}{x})^{n-i}x^n=x^nA(\dfrac{1}{x})\)

将 \(\dfrac{1}{x}\) 代入题目中式子：

\[\begin{aligned} F(\dfrac{1}{x})&=Q(\dfrac{1}{x})\times G(\dfrac{1}{x})+R(\dfrac{1}{x})\\ \\ x^n\times F(\dfrac{1}{x})&=x^n\times Q(\dfrac{1}{x})\times G(\dfrac{1}{x})+x^n\times R(\dfrac{1}{x})\\ \\ x^nF(\dfrac{1}{x})&=x^{n-m} Q(\dfrac{1}{x})\times x^mG(\dfrac{1}{x})+x^{n-m+1}\times x^{m-1}R(\dfrac{1}{x})\\ \\ F_r(x)&= Q_r(x)\times G_r(x)+x^{n-m+1}R_r(x)\\ \\ F_r(x)&\equiv Q_r(x)\times G_r(x)\pmod {x^{n-m+1}}\\ \\ Q_r(x)&\equiv F_r(x)\times G_r^{-1}(x)\pmod {x^{n-m+1}}\\ \\ \end{aligned}\]

\(Q_r(x)\) 翻转即为 \(Q(x)\)，\(R(x)=F(x)-Q(x)\times G(x)\)。

---

P4725 多项式 ln

\[\begin{aligned} F(x)&\equiv\ln A(x)\\ \\ F'(x)&\equiv\dfrac{1}{A(x)}\times A'(x)\\ \\ F(x)&\equiv\int\dfrac{1}{A(x)}\times A'(x)\text{ d}x\\ \\ \end{aligned}\]

---

P4726 多项式 exp

\[F(x)\equiv e^{A(x)}\pmod{x^n} \]

两边求对数后移项得

\[\ln F(x)-A(x)\equiv 0\pmod{x^n} \]

令 \(G(F(x))=\ln F(x)-A(x)\)，代入牛顿迭代的式子：

\[F(x)=F_0(x)-\dfrac{\ln F(x)-A(x)}{G'(F(x))} \]

\(G'F(x)=F^{-1}(x)\)，代入得

\[F(x)=F_0(x)(1-\ln F(x)+A(x)) \]

初始时 \(F_0(x)=e^0=1\)。

标签：推导,pmod,dfrac,times,公式,多项式,aligned,equiv
From： https://www.cnblogs.com/ConvergentSeries/p/17973399