牛顿迭代

问题描述

已知函数 \(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)\) 处进行泰勒展开：

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

然后对 \(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})\) 。

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

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

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

然后我们就可以根据这个等式倍增求解了，每次算出上一层的 \(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[0]=1,g[0]=0\) ，答案对 \(998244353\) 取模。

Solution

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

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

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

我们可以得到：

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

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

多项式对数函数（多项式 \(\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\) 。

根据链式法则，我们有：

所以我们只需要对 \(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\) ，可以得到：

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

代入牛顿迭代的公式得：

因为 \(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)\) 的区别是系数翻转了。

开始推式子：

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

然后 \(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)\) ，满足：

显然，我们有：

多项式快速幂

问题描述

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

Solution

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

多项式学习合集

原文：https://www.cnblogs.com/TheShadow/p/13144395.html