多项式学习合集

牛顿迭代

问题描述

已知函数 (G(x)) ，求一个多项式 (F(x) mod x^n) 满足 (G(F(x))equiv 0 (mod x^n)) 。

Solution

我们假设已经求出 (G(F_0(x))equiv 0 (mod x^{lceilfrac{n}{2} ceil})) ，考虑如何拓展到 (mod x^n) 下。

我们把 (G(F(x))) 在 (F_0(x)) 处进行泰勒展开：

[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+cdots ]

因为 (F(x)) 和 (F_0(x)) 的最后 (lceilfrac{n}{2} ceil) 项相同，所以 ((F(x)-F_0(x))^2) 最低非 (0) 项系数大于 (2cdotlceilfrac{n}{2} ceil) ，所以可以得到：

[G(F(x))equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x)) (mod x^n)\ F(x)equiv F_0(x)-frac{G(F_0(x))}{G'(F_0(x))} ]

然后对 (n=1) 的时候，我们单独求出满足条件的 (F(x)) 即可递推出答案。

多项式求逆

问题描述

给出 (F(x)) ，求出 (G(x)) ，使得 (F(x)cdot G(x)equiv 1 (mod x^n)) ，系数对 (998244353) 取模。

Solution

我们设 (H(x)) 满足 (F(x)cdot H(x)equiv 1 (mod x^{lceilfrac{n}{2} ceil})) 。

而显然 (F(x)cdot G(x)equiv 1 (mod x^{lceilfrac{n}{2} ceil})) 。

两者相减，我们可以得到 (F(x)cdot(G(x)-H(x))equiv 0 (mod x^{lceilfrac{n}{2} ceil})) 。

所以 (G(x)-H(x)equiv 0 (mod x^{lceilfrac{n}{2} ceil})) 。

我们将等式平方，可以得到：

[G(x)^2-2cdot G(x)H(x)+H(x)^2equiv 0 (mod x^n) ]

同时乘上 (F(x)) ，则：

[F(x)cdot G(x)^2-2cdot F(x)cdot G(x)cdot H(x)+F(x)cdot H(x)^2equiv 0 (mod x^n) ]

因为 (F(x)cdot G(x)=1) ，所以我们有：

[G(x)equiv 2cdot H(x)-F(x)cdot H(x)^2 (mod x^n) ]

然后我们就可以根据这个等式倍增求解了，每次算出上一层的 (H(x)) ，然后推出 (G(x)) ，时间复杂度为 (O(nlog n)) 。

分治 (FFT)

问题描述

已知一个长度为 (n) 的数组 (g[0],g[1],cdots,g[n-1]) ，求 (f[0],f[1],cdots,f[n-1]) ，其中：

[f[i]=sum_{j=1}^if[i-j]cdot g[j] ]

边界为 (f[0]=1,g[0]=0) ，答案对 (998244353) 取模。

Solution

我们先对 (f[i]) 的递推式变一下形。

[f[i]=sum_{j=0}^{i} f[i-j]cdot g[j] ]

因为 (g[0]=0) ，所以上下是完全等价的。

我们设 (F(x),G(x)) 分别为数组 (f,g) 的生成函数。

我们可以得到：

[F(x)cdot G(x)=sum_{i=0}^{infin} x^isum_{j=0}^i f[i-j]cdot g[j]\ =sum_{i=1}^{infin}f[i-1]cdot x^i ]

可以发现和 (F(x)) 相比，我们有：

[F(x)cdot G(x)=F(x)-f[0]\ F(x)cdot(1-G(x))=f[0]\ F(x)=f[0]cdot (1-G(x))^{-1}=(1-G(x))^{-1} ]

然后就可以直接上多项式求逆的模板了。

多项式对数函数（多项式 (ln) ）

问题描述

给出一个 (n-1) 次多项式 (A(x)) ， 求一个 (mod x^n) 下的多项式 (B(x)) ，满足 (B(x)=ln A(x)) 。

Solution

我们定义 (G(x)=F(A(x)),F(x)=ln x) 。

根据链式法则，我们有：

[G'(x)=F'(A(x))cdot A'(x)\ G'(x)=frac{A'(x)}{A(x)} ]

所以我们只需要对 (A(x)) 求逆，即可算出 (G'(x)) 。

由于求导和不定积分是互逆的，所以我们再对 (G’(x)) 求一个积分即可得到 (G(x)) 。

• 求导公式： (F(x)=x^n,F'(x)=ncdot x^{n-1}) 。
• 积分公式： (int x^ndx=frac{1}{n+1}x^{n+1}) 。

多项式指数函数（多项式 (exp) ）

问题描述

给出一个 (n-1) 次多项式，求一个 (mod x^n) 下的多项式 (B(x)) ，满足 (B(x)equiv e^{A(x)}) 。

Solution

我们先对原式取一个 (ln) ，可以得到：

[ln B(x)-A(x)=0 ]

我们设 (G(B(x))=ln B(x)-A(x)) ，那么就要求这一个函数的零点。我们将 (B(x)) 看做变量， (A(x)) 看做常量，对 (G(B(x))) 求导，可以得到 (G'(B(x))=frac{1}{B(x)}) 。

代入牛顿迭代的公式得：

[B(x)equiv B_0(x)-frac{G(B_0(x))}{G'(B_0(x))} (mod x^n)\ B(x)equiv B_0(x)(1-ln B_0(x)+A(x)) (mod x^n) ]

因为 (A(0)=0) ，所以 (B(x)) 的常数项为 (1) ，剩下的就是各种板子了。

多项式除法

问题描述

给定一个 (n) 次多项式 (F(x)) 和一个 (m) 次多项式 (G(x)) ，请求出多项式 (Q(x),R(x)) ，满足一下条件：

• (Q(x)) 的次数为 (n-m) ， (R(x)) 的次数小于 (m)
• (F(x)=Q(x)cdot G(x)+R(x)) 。

Solution

假设 (A(x)) 为一个 (n) 次多项式，我们这样定义 (A_r(x)) ：

• (A_r(x)=x^ncdot A(frac{1}{x})) 。

显然，我们可以得到 (A_r(x),A(x)) 的区别是系数翻转了。

开始推式子：

[F(x)=Q(x)cdot G(x)+R(x)\ F(frac{1}{x})=Q(frac{1}{x})cdot G(frac{1}{x})+R(frac{1}{x})\ x^ncdot F(frac{1}{x})=x^{n-m}cdot Q(frac{1}{x})cdot x^mcdot G(frac{1}{x})+x^{n-m+1}cdot x^{m-1}cdot R(frac{1}{x})\ F_r(x)=Q_r(x)cdot G_r(x)+x^{n-m+1}cdot R_r(x) ]

在模 (x^{n-m+1}) 的意义下，我们可以得到：

[F_r(x)=Q_r(x)cdot G_r(x)\ Q_r(x)=frac{F_r(x)}{G_r(x)} ]

然后 (R(x)=F(x)-G(x)cdot Q(x)) 。

多项式开根

问题描述

给定一个 (n-1) 次多项式 (A(x)) ，求一个在 (mod x^n) 意义下的多项式 (B(x)) ，使得 (B^2(x)equiv A(x) (mod x^n)) 。若有多解，请取零次项系数较小的作为答案。

Solution

我们假设已经求出一个 (H(x)) ，满足：

[H^2(x)equiv A(x) (mod x^{lceilfrac{n}{2} ceil}) ]

显然，我们有：

[H(x)equiv G(x) (mod x^{lceilfrac{n}{2} ceil})\ H(x)-G(x)equiv 0 (mod x^{lceilfrac{n}{2} ceil})\ H^2(x)-2cdot H(x)cdot G(x)+G^2(x)equiv 0 (mod x^n)\ A(x)-2cdot H(x)cdot G(x)+H^2(x)equiv 0 (mod x^n)\ G(x)=frac{A(x)+H^2(x)}{2cdot H(x)}\ G(x)=frac{A(x)cdot H'(x)+H(x)}{2} ]

多项式快速幂

问题描述

给定一个 (n-1) 次多项式，求一个在 (mod x^n) 意义下的多项式 (B(x)) ，使得 (B(x)equiv A^k(x) (mod x^n)) 。

Solution

两边取 (ln) ，可以得到：

[ln B(x)equiv kln A(x) (mod x^n)\ B(x)equiv e^{kln A(x)} (mod x^n) ]