多项式求逆元

概述

多项式求逆元是多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 \mathcal O(n\log n) 的时间内求出一个多项式的逆元

基本概念

在介绍多项式的逆元之前,先说明一些概念:多项式的度、多项式的逆元、多项式的除法和取余

对于一个多项式 A(x),称其最高项的次数为这个多项式的(degree),记作 deg A

对于多项式 A(x), B(x),存在唯一Q(x), R(x) 满足 A(x) = Q(x)B(x) + R(x),其中 deg R < deg B,我们称 Q(x)B(x)A(x)R(x)B(x)A(x)余数,可以记作

 A(x) \equiv R(x) \pmod {B(x)}

多项式的逆元

对于一个多项式 A(x),如果存在 B(x) 满足 deg B \leq deg A 并且

 A(x)B(x) \equiv 1 \pmod {x^n}

那么称 B(x)A(x)\bmod x^n 意义下的逆元(inverse element),记作 A^{-1}(x)

求解过程

现在考虑如何求 A^{-1}(x),当 n=1 时,A(x) \equiv c \pmod xc 是一个常数,这样,A^{-1}(x) 就是 c^{-1}

对于 n>1 的情况,设 B(x) = A^{-1}(x) 由定义可以知道

 \begin{equation} \label{eqn1} A(x)B(x) \equiv 1 \pmod {x^n} \end{equation}

假设在 \bmod x^{\lceil \frac{n}{2} \rceil} 意义下 A(x) 的逆元是 B'(x) 并且我们已经求出,那么

 \begin{equation} \label{eqn2} A(x)B'(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}} \end{equation}

再将 (\ref{eqn1}) 放到 \bmod x^{\lceil \frac{n}{2} \rceil} 意义下

 \begin{equation} \label{eqn3} A(x)B(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}} \end{equation}

然后 (\ref{eqn2}) - (\ref{eqn3}) 就可以得到

 B(x) - B'(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}

两边平方

 B^2(x) - 2B'(x)B(x) + B'^2(x) \equiv 0 \pmod {x^n}

这里解释一下平方后为什么模的 x^{\lceil \frac{n}{2} \rceil} 也会平方,这是因为,左边多项式在 \bmod x^n 意义下为 0,那么就说明其 0n-1 次项系数都为 0,平方了之后,对于第 0 \leq i \leq 2n-1 项,其系数 a_i\sum_{j=0}^i a_ja_{i-j},很明显 ji-j 之间必然有一个值小于 n,因此 a_i 必然是 0,也就是说平方后在 \bmod x^{2n} 意义下仍然为 0

然后同时乘上 A(x),移项可以得到

 B(x) \equiv 2B'(x) - A(x)B'^2(x) \pmod {x^n}

这样就可以得到 \bmod x^n 意义下的逆元了,利用 FFT 加速之后可以做到在 \mathcal O(n\log n) 时间内解决当前问题,最后总的时间复杂度也就是

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

顺便一提,由这个过程可以看出,一个多项式有没有逆元完全取决于其常数项是否有逆元

代码实现

假设我已经有了计算快速傅里叶变换的函数 transform(int deg, complex_t* x, complex_t* w) 以及单位根表 epsinv_eps

下面是数论版的,并且是完整的代码实现

 应用

预处理 Bernoulli 数

Bernoulli 数的指数生成函数(EGF)是

 \frac{x}{e^x-1}=\sum_{i=0}^\infty B_i \frac{x^i}{i!}

e^x 泰勒展开就可以改写成

 \frac{x}{e^x-1}=\frac{1}{\sum_{i=0}^\infty \frac{x^i}{(i+1)!}}

然后利用刚刚所说的方法,求出这个多项式的逆元就可以得到 Bernoulli 数了

计算有标号简单连通无向图个数

这篇文章,在列出方程后最后可以用多项式求逆优化

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/polynomial-inverse

miskcoo

顺利从福州一中毕业! 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

13 thoughts on “多项式求逆元

  1. 「平方后为什么模的 $x^{\lceil \frac{n}{2} \rceil}$ 也会平方」那里讲得太绕了

    我可能会这样讲:根据 $B(x) - B'(x) \equiv 0 \pmod {x^{\lceil n/2 \rceil}}$,左边一定是一个形如 $k\cdot x^{\lceil n/2 \rceil}$ 的多项式,它的平方(即 $(B(x) - B'(x))^2$)为 $k^2x^n$($n$ 为偶数)或 $k^2x^{n+1}$($n$ 为奇数) ,显然二者均能被 $x^n$ 整除

  2. 请问博主,“n = 1 时 A(x) = c (mod x) 此时 A 的逆就是 c 的逆“那一块,c 是常量,x 是变量,为什么 c 在模 x 意义下会有逆

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.