多项式求逆元

概述

多项式求逆元是多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 \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)}

(more…)

Read More