多项式学习合集

牛顿迭代

问题描述

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

Solution

我们假设已经求出 $G(F_0(x))\equiv 0\ (mod\ x^{\lceil\frac{n}{2}\rceil})$ ，考虑如何拓展到 $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)$ 的最后 $\lceil\frac{n}{2}\rceil$ 项相同，所以 $(F(x)-F_0(x))^2$ 最低非 $0$ 项系数大于 $2\cdot\lceil\frac{n}{2}\rceil$ ，所以可以得到：

$$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^{\lceil\frac{n}{2}\rceil})$ 。

而显然 $F(x)\cdot G(x)\equiv 1 \ (mod\ x^{\lceil\frac{n}{2}\rceil})$ 。

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

所以 $G(x)-H(x)\equiv 0\ (mod\ x^{\lceil\frac{n}{2}\rceil})$ 。

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

$$G(x)^2-2\cdot G(x)H(x)+H(x)^2\equiv 0\ (mod\ x^n)$$

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

$$F(x)\cdot G(x)^2-2\cdot F(x)\cdot G(x)\cdot H(x)+F(x)\cdot H(x)^2\equiv 0\ (mod\ x^n)$$

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

$$G(x)\equiv 2\cdot H(x)-F(x)\cdot H(x)^2\ (mod\ x^n)$$

然后我们就可以根据这个等式倍增求解了，每次算出上一层的 $H(x)$ ，然后推出 $G(x)$ ，时间复杂度为 $O(n\log 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+1} 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^i\sum_{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)=n\cdot 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^n\cdot 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^n\cdot F(\frac{1}{x})=x^{n-m}\cdot Q(\frac{1}{x})\cdot x^m\cdot 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^{\lceil\frac{n}{2}\rceil})$$

显然，我们有：

$$H(x)\equiv G(x)\ (mod\ x^{\lceil\frac{n}{2}\rceil})\\ H(x)-G(x)\equiv 0\ (mod\ x^{\lceil\frac{n}{2}\rceil})\\ H^2(x)-2\cdot H(x)\cdot G(x)+G^2(x)\equiv 0\ (mod\ x^n)\\ A(x)-2\cdot H(x)\cdot G(x)+H^2(x)\equiv 0\ (mod\ x^n)\\ G(x)=\frac{A(x)+H^2(x)}{2\cdot 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 k\ln A(x)\ (mod\ x^n)\\ B(x)\equiv e^{k\ln A(x)}\ (mod\ x^n)$$