With Passion and Love

多项式全家桶

多项式全家桶

不知道为啥公式字体这么大。。
先放在这里,写完了再来修(或者不修)
写完放到ext-x.me上应该会方便阅读。

多项式求逆

对于$n$次多项式$F(x)$,求$F'(x)$使得$F(x)F'(x) \equiv 1 \pmod {x^n}$

$$F(x)F'(x)\equiv 1\pmod {x^n}$$

假设我们已经求出来了$F_0(x)$满足

$$F(x)F_0(x)\equiv 1 \pmod {x^{\lceil\frac{n}{2}\rceil}}​$$

两个式子相减

$$F'(x)-F_0(x)\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}​$$

然后两边平方

$$F’^2(x)-F_0^2(x)+2F'(x)F_0(x)\equiv 0 \pmod {x^{n}}​$$

因为$F(x)-F_0(x)$的前$\lceil\frac{n}{2}\rceil$项都是$0$,乘起来$h_{i+j}=\sum f_{i}g_{j}$,对于$0\sim n$项中的第$x$项,必然有是由两项的乘积加起来的,但是由于$a+b=x$,$ab$之中必然有一个小于$\lceil\frac{n}{2}\rceil$,为0,所以得到在模$x^n$下为$0$。

然后把原式子两边乘上$F(x)$消去$F'(x)$

$$\begin{aligned}F'(x)&-F_0^2(x)+2F_0(x) \equiv 0 \pmod {x^n}\F'(x)&\equiv F_0^2(x)-2F_0(x) \pmod {x^n}\F'(x)&\equiv F_0(F_0(x)-2) \pmod {x^n}\end{aligned}​$$

注意边界情况$F'[0]=\text{inverse}(F[0])​$

复杂度$T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)​$

递归版实现

非递归版实现

多项式开方

对于一个$n​$次的多项式$F(x)​$考虑求一个函数$G(x)​$,使得$G(F(x))\equiv 0\pmod {x^n}​$

$$G(F(x))=\sum_{i=0}^{n}[g_i({\sum_{i=0}^{n}x^if_i})^i]​$$

还是根据上面的思路,假设我们已知$G(F_0(x))\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}​$。

将$G(F(x))​$在$F_0(x)​$这里泰勒展开

$$\begin{aligned}G(F(x))=&G(F_0(x))\+&\frac{G'(F_0(x))}{1!}(F(x)-F_0(x))\+&\frac{G”(F_0(x))}{2!}(F(x)-F_0(x))^2\+&~…..\end{aligned}$$

因为$F(x)​$和$F_0(x)​$第$0\sim \lceil\frac{n}{2}\rceil​$在模$x^n​$下相等,类似多项式求逆,可知$(F(x)-F(x_0))^2​$的最低非零项大于$2\lceil\frac{n}{2}\rceil​$,所以后面的可以直接忽略。

因为$G(F(x))\equiv 0 \pmod {x^n}$

整理一下式子

$$\begin{aligned}G(F(x))&=G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\0&\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod {x^n}\0&\equiv\frac{G(F_0(x))}{G'(F_0(x))}+F(x)-F_0(x)\pmod {x^n}\F(x)&\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))} \pmod {x^n}\end{aligned}​$$

对于多项式开方,我们对于$n$次多项式$A(x)$求多项式$B(x)$满足

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

因为$B^2(x)-A(x)\equiv 0\pmod {x^n}​$,所以对于$B(x)​$,构造$G(B(x))\equiv 0 \equiv B^2(x)-A(x)\pmod {x^n}​$

把$B(x)$作为$G$函数的变量可得$G(B(x))\equiv B^2(x)-A(x)$,$G'(x)\equiv 2B(x)$

$$\begin{aligned}B(x)&\equiv B_0(x)-\frac{B_0^2(x)-A(x)}{2B_0(x)} \pmod {x^n} \&\equiv \frac{B_0^2(x)+A(x)}{2B_0(x)}\end{aligned}​$$

关于常数项不为$1$的时候需要求二次剩余

其实多项式开方还可以用多项式次方来计算,这个后面会说到。

复杂度同上$O(nlogn)

多项式求导&积分

根据求导公示

$$x^i=ix^{i-1}$$

积分公式

$$\int x^idx=\frac{1}{i+1}x^{i+1}$$

可以直接$O(n)$求得,这个比较简单,每一个一行就能写完

多项式对数函数

对于$n​$次多项式$A(x)​$,求$B(x)​$满足$B(x)\equiv \ln A(x) \pmod {x^n}​$

$$(\ln A(x))’=\ln'(A(x))A'(x)=\frac{A'(x)}{A(x)}$$

$$\ln(A(x))=\int A'(x)=\int \frac{A'(x)}{A(x)}$$

复杂度$O(nlogn)

多项式指数函数

对于$n$次多项式$A(x)$,求$B(x)$满足$B(x)\equiv \exp A(x) \pmod {x^n}$

$$\begin{aligned}B(x)&=\exp A(x)\\ln B(x)&=A(x)\ \ln B(x)&-A(x)=0 \end{aligned}$$

构造$G(x)=\ln B(x)-A(x)$,有$G'(x)=\frac{1}{B(x)}$

类似多项式开根的思路

$$\begin{aligned}B(x)&\equiv B_0(x)-\frac{G(B_0(x)}{G'(B_0(x)}\ &\equiv B_0(x)-\frac{\ln B_0(x)-A(x)}{\frac{1}{B_0(x)}}\&\equiv B_0(x)-B_0(\ln B_0(x)-A(x))\&\equiv B_0(x)(1-\ln B_0(x)+A(x)) \pmod {x^n}\end{aligned}$$

复杂度$O(nlogn)



Leave a Reply

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