多项式学习笔记

预备知识

快速傅里叶变换和快速数论变换。

多项式的加减乘。

多项式求逆

多项式$A=\sum_{i=0}^{\inf}a_{i}x^{i},在同余$P$和模$[n]=x^{n}$下,

有(计作)$A\times A^{-1}=1\space ([n])$,则$A^{-1}$被称为$A$的逆。

 

采用分治的思想,首先我们处理出$A$在$(\lceil \frac{n}{2} \rceil)$下的逆元$B$,

又因为$AA^{-1}=1\space (\lceil \frac{n}{2} \rceil)$,

所以说$A^{-1}-B=0\space (\lceil \frac{n}{2} \rceil)$。

接下来两侧同时平方:$A^{-2}-2A^{-1} B+B^2=0\space (\lceil \frac{n}{2} \rceil)$

乘上$A$:$A^{-1}-2B+AB^2=0\space (\lceil \frac{n}{2} \rceil)$

移项可得:$A^{-1}=2B+AB^2=0\space (\lceil \frac{n}{2} \rceil)$

我们就可以使用多项式乘法求逆了!!!

(无比丑陋)

多项式除法

多项式除法即$A(x)=B(x)C(x)+R(x)$,$A(x)$为系数已知的$n$次多项式,

$B(x)$为系数已知的$m\leq n$次多项式,求$C(x)$和$R(x)$。

 

首先我们定义$A^{r}(x)$表示将$A(x)$的系数翻转后的结果,可以表示为$A^{r}(x)=x^{n}A(\frac{1}{x})$。

那么原式等于$x^{n}A(\frac{1}{x})=x^mB(\frac{1}{x})x^{n-m}C(\frac{1}{x})+x^(n-m+1)x^{m-1}R(\frac{1}{x})$

等价于$A^{r}(x)=B^{r}(x)C^{r}(x)+x^{n-m+1}R^{r}(x)$。

我们可以发现,多项式$C^{r}(x)$次数不超过$n-m$,我们同时对等式两侧模$x^{n-m+1}$。

$A^{r}(x)=B^{r}(x)C^{r}(x)\space\space mod \space [x^{n-m+1}]$。

我们就可以通过多项式求逆轻松求出$C(x)$进一步解出$R(x)$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注