算法学习笔记(17)：多项式反三角函数

给定多项式 f\left(x\right)，求模 x^{n} 意义下的 \arcsin{f\left(x\right)}, \arccos{f\left(x\right)} 与 \arctan{f\left(x\right)}。

同求解多项式\ln，先对\arcsin x求导，然后积分：

\begin{aligned} \frac{\mathrm{d}\arcsin{x}}{\mathrm{d} x} &= \frac{1}{\sqrt{1 - x^{2}}} \\ {\mathrm{d} } \arcsin{x} &= \frac{1}{\sqrt{1 - x^{2}}}{\mathrm{d} x} \\ \arcsin{x} &= \int \frac{1}{\sqrt{1 - x^{2}}} \mathrm{d} x \\\end{aligned}

同理，对于\arccos x有：

\begin{aligned} \frac{\mathrm{d}\arccos{x}}{\mathrm{d} x} &= - \frac{1}{\sqrt{1 - x^{2}}} \\ {\mathrm{d}\arccos{x}} &= - \frac{1}{\sqrt{1 - x^{2}}}\mathrm{d} x \\ \arccos{x} &= - \int \frac{1}{\sqrt{1 - x^{2}}} \mathrm{d} x \\\end{aligned}

同理，对于\arctan x有

\begin{aligned} \frac{\mathrm{d}\arctan{x} }{\mathrm{d} x} &= \frac{1}{1 + x^{2}} \\{\mathrm{d} } \arctan{x} &= \frac{1}{1 + x^{2}}{\mathrm{d} x} \\ \arctan{x} &= \int \frac{1}{1 + x^{2}} \mathrm{d} x\end{aligned}

然后我们将x换元成f(x)可以得到：

\begin{aligned} \frac{\mathrm{d}}{\mathrm{d} x} \arcsin{f\left(x\right)} &= \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \\ \arcsin{f\left(x\right)} &= \int \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arccos{f\left(x\right)} &= - \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \\ \arccos{f\left(x\right)} &= - \int \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arctan{f\left(x\right)} &= \frac{f'\left(x\right)}{1 + f^{2}\left(x\right)} \\ \arctan{f\left(x\right)} &= \int \frac{f'\left(x\right)}{1 + f^{2}\left(x\right)} \mathrm{d} x\end{aligned}

方程右边涉及了多项式求导、多项式乘法、多项式加法、多项式求逆、多项式积分。这些东西都是我们学过的，这些操作除了求逆、开方、乘法是O(n\log n)以外其余均是O(n)的

所以我们可以在O(n\log n)内求出任意一个多项式反三角函数

多项式反三角函数模板题，带入上述公式即可，完整代码见文末（太感人了，总算不被卡常了）

然后我们就成功又水了一道黑题(bushi)（划掉）