「Learning Notes」多项式求逆

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Description

给定多项式 f(x) ,求 f^{-1}(x)

Methods

倍增法

首先,易知

\left[x^{0}\right] f^{-1}(x) = \left(\left[x^{0}\right] f(x)\right)^{-1}

假设现在已经求出了 f(x) 在模 x^{\left\lceil\frac{n}{2}\right\rceil} 意义下的逆元 f^{-1}_{0}(x)
有:

\begin{aligned} f(x) f^{-1}_{0}(x) & \equiv 1 & \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ f(x) f^{-1}(x) & \equiv 1 & \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ f^{-1}(x) - f^{-1}_{0}(x) & \equiv 0 & \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} \end{aligned}

两边平方可得:

f^{-2}(x) - 2 f^{-1}(x) f^{-1}_{0}(x) + f^{-2}_{0}(x) \equiv 0 \pmod{x^{n}}

两边同乘 f(x) 并移项可得:

f^{-1}(x) \equiv f^{-1}_{0}(x) \left(2 - f(x) f^{-1}_{0}(x)\right) \pmod{x^{n}}

递归计算即可。

时间复杂度

T(n) = T\left(\frac{n}{2}\right) + O(n \log{n}) = O(n \log{n})

Newton's Method

参见 Newton's Method.

Examples

  1. 求 Bernoulli 数
  2. 有标号简单无向连通图计数