多项式求逆
描述¶
给定多项式 f\left(x\right),求 f^{-1}\left(x\right)。
解法¶
倍增法¶
首先,易知
\left[x^{0}\right]f^{-1}\left(x\right)=\left(\left[x^{0}\right]f\left(x\right)\right)^{-1}
假设现在已经求出了 f\left(x\right) 在模 x^{\left\lceil\frac{n}{2}\right\rceil} 意义下的逆元 f^{-1}_{0}\left(x\right)。 有:
\begin{aligned}
f\left(x\right)f^{-1}_{0}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
f\left(x\right)f^{-1}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\
f^{-1}\left(x\right)-f^{-1}_{0}\left(x\right)&\equiv 0 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}
\end{aligned}
两边平方可得:
f^{-2}\left(x\right)-2f^{-1}\left(x\right)f^{-1}_{0}\left(x\right)+f^{-2}_{0}\left(x\right)\equiv 0 \pmod{x^{n}}
两边同乘 f\left(x\right) 并移项可得:
f^{-1}\left(x\right)\equiv f^{-1}_{0}\left(x\right)\left(2-f\left(x\right)f^{-1}_{0}\left(x\right)\right) \pmod{x^{n}}
递归计算即可。
时间复杂度
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
Newton's Method¶
参见 Newton's Method.
Graeffe 法¶
欲求 f^{-1}(x)\bmod x^{2n} 考虑
\begin{aligned}
f^{-1}(x)\bmod x^{2n}&= f(-x)(f(x)f(-x))^{-1}\bmod x^{2n}\\
&=f(-x)g^{-1}(x^2)\bmod x^{2n}
\end{aligned}
只需求出 g^{-1}(x)\bmod x^n 即可还原出 g^{-1}(x^2)\bmod x^{2n} 因为 f(x)f(-x) 是偶函数,时间复杂度同上。
代码¶
多项式求逆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
例题¶
- 有标号简单无向连通图计数:「POJ 1737」Connected Graph
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用