多项式基础总结

· · 个人记录

欧拉公式：

e^{ix}=\cos{x}+i\sin{x}

求导：

x^n \dfrac{\text{d}y}{\text{d}x}=nx^{n-1}

积分：

\int x^n \text{d}x=\dfrac{1}{n+1}x^{n+1}

求逆：

边界条件直接求逆元即可。

设 H(x) 满足 H(x)\equiv \dfrac{1}{F(x)} \pmod{x^{\lceil\frac{n}{2}\rceil}}，G(x) 满足 G(x)\equiv \dfrac{1}{F(x)} \pmod{x^n}，那么有：

F(x)G(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}} F(x)H(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}} F(x)(G(x)-H(x))\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}} G(x)-H(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}

两边同时平方，因为 G(x)-H(x) 在 0 到 \lceil\frac{n}{2}\rceil-1 次项都为 0，所以 (G(x)-H(x))^2 的 \lceil\frac{n}{2}\rceil 到 n-1 次项的系数中至少一项为 0，因此：

G(x)^2+H(x)^2-2G(x)H(x)\equiv 0\pmod{x^n}

两边同乘 F(x)：

G(x)+H(x)^2F(x)-2H(x)\equiv 0\pmod{x^n} G(x)\equiv 2H(x)-H(x)^2F(x)\pmod{x^n}

递归解决即可。

设 $G(x)=\ln{}(F(x))$，则由链式法则得 $G'(x)=\dfrac{F'(x)}{F(x)}$，求逆再积分回来即可。 $\exp$： 递归，边界条件直接构造。 设 $\ln{H(x)}\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}$，$\ln{G(x)}\equiv F(x)\pmod{x^n}

也就是求关于多项式的函数 f(G(x))=\ln G(x)-F(x) 的零点。

根据牛顿迭代公式有 x=x_0-\dfrac{f(x)}{f'(x)}，那么：

G(x)=H(x)-\dfrac{\ln{H(x)}-F(x)}{\dfrac{1}{H(x)}}=H(x)(1-\ln{H(x)}+F(x))

因为每迭代一次精度翻倍，因此这个算法的正确性是有保证的。

开根：

递归，边界条件直接构造。

设 H(x)^2\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}，G(x)^2\equiv F(x)\pmod{x^n}，那么：

G(x)^2\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}} G(x)-H(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}} G(x)^2+H(x)^2-2G(x)H(x)\equiv 0\pmod{x^n} F(x)+H(x)^2-2G(x)H(x)\equiv 0\pmod{x^n} G(x)=\dfrac{F(x)+H(x)^2}{2H(x)}=\dfrac{H(x)}{2}+\dfrac{F(x)}{2H(x)}

递归实现即可。

幂函数：

去掉前面系数为 0 的项，提出系数来，使 F_0=1，先 \ln，整体乘 k，再 \exp，最后乘上系数再右移即可。

除法：

F(x)=G(x)Q(x)+R(x) x^nF(\dfrac{1}{x})=x^mG(\dfrac{1}{x})x^{n-m}Q(\dfrac{1}{x})+x^{n-m+1}x^{m-1}R(\dfrac{1}{x}) F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}R_R(x) F_R(x)\equiv G_R(x)Q_R(x)\pmod{x^{n-m+1}} G_R(x)\equiv \dfrac{F_R(x)}{Q_R(x)}\pmod {x^{n-m+1}}

因为 Q 的次数为 n-m<n-m+1，因此答案不受影响。

求逆计算即可。