多项式的几个板子,代码也放在一起了.
Luogu P4238 多项式求逆
给定一个 $n$ 项的多项式 $A$ ,求多项式 $B$ ,使得 $A\cdot B\equiv 1 (\mbox{mod}\ x^n)$ .
首先还是用 $0$ 将 $n$ 补成 $2$ 的幂次,然后递归求解.
若 $n=1$ ,那么只需要让 $B=A_0^{-1}$ .
若 $n>1$ ,则先求解 $B’$ ,使得 $A\cdot B’\equiv 1(\mbox{mod}\ x^{\frac n 2})$ .
因为 $A\cdot B\equiv 1(\mbox{mod}\ x^n)$ ,所以有 $B-B’\equiv 0(\mbox{mod}\ x^{\frac n 2})$ .
即 $B-B’=C\cdot x^{\frac n 2}$ ,所以 $B^2-2\cdot B\cdot B’+B’^2\equiv 0(\mbox{mod}\ x^n)$ .
两边同乘 $A$ ,得到 $B-2B’+A\cdot B’^2\equiv 0(\mbox{mod}\ x^n)$ .
于是可以得到 $B\equiv 2B’-A\cdot B’^2(\mbox{mod}\ x^n)$ . 可以看出,多项式 $A$ 有逆元的充要条件是常数项 $A_0$ 有逆元.
时间复杂度为 $\Theta(n\log n)$ .
实现时可以把递归改成迭代,常数会优秀许多.
Luogu 4721 分治FFT
可以考虑 cdq 分治,每次处理 $[l,mid)$ 对 $[mid,r)$ 的贡献,时间复杂度 $O(n\log^2 n)$ .
另一个做法是记 $F,G$ 分别表示数列 $f,g$ 的生成函数,将它们卷起来,可以发现 $F(x)G(x)=F(x)-F(0)$ .
则 $F(x)=\frac{F(0)}{1-G(x)}$ ,写个多项式求逆,时间复杂度 $O(n\log n)$ .
Luogu P4512 多项式除法/多项式取模
给定一个 $n$ 次多项式 $A$ ,一个 $m$ 次多项式 $B$ ,满足 $m\le n$ ,求多项式 $D,R$ ,使得,
$$
A(x)=D(x)B(x)+R(x)
$$
并且 $\deg (D)\le n-m,\deg (R)<m$ .
尝试先消去余式 $R(x)$ 的影响,考虑多项式的 系数反转 ,即对于一个 $n$ 次多项式 $A$ ,
$$
A^R(x)=x^n\cdot A(\frac 1 x)
$$
如 $A(x)=x^3+2x^2+3x+4$ ,则 $A^R(x)=x^3\cdot A(\frac 1 x)=4x^3+3x^2+2x+1$ .
我们要求满足 $A(x)=D(x)B(x)+R(x)$ 的 $D,R$ ,如果将 $x$ 全部用 $\frac 1 x$ 替换,等式仍然成立.
替换后同时乘上 $x^n$ ,由于 $\deg(D)\le n-m,\deg(R)<m$ ,将 $D,R$ 次数分别看做 $n-m,m-1$ ,用 $0$ 补够.
于是可以得到,
$$
A^R(x)=D^R(x)B^R(x)+x^{n-m+1}\cdot R^R(x)
$$
我们将上面的等式两边都对 $x^{n-m+1}$ 取模, $x^{n-m+1}\cdot R^R(x)$ 就被消去了,于是得到,
$$
A^R(x)\equiv D^R(x)B^R(x) (\mbox{mod}\ x^{n-m+1})
$$
对 $B^R(x)$ 用一次多项式求逆,再用一次多项式乘法求得模 $x^{n-m+1}$ 意义下的 $D^R(x)$ .
由于 $\deg (D)\le n-m$ ,反转后 $\deg (D^R)\le n-m$ .所以模意义下求得的 $D^R(x)$ 就是真实的 $D^R(x)$ .
再系数反转求得 $D(x)$ ,回代 $A(x)=D(x)B(x)+R(x)$ 得到 $R(x)$ .
从上述过程可以看出,多项式除法/多项式取模的时间复杂度与多项式求逆相同,为 $\Theta(n\log n)$ .
Luogu P4728 多项式 $\ln$
首先需要了解多项式的求导和不定积分.对于一个 $n-1$ 次多项式 $A$ ,
$$
A(x)=\sum_{i=0}^{n-1} a_i\cdot x_i\\
A’(x)=\sum_{i=0}^{n-2} a_{i+1}\cdot(i+1)\cdot x^i \\
\int A(x) \mbox d x=\sum_{i=1}^{n}\frac {a_{i-1}} i \cdot x^i+C
$$
现在给出 $n-1$ 次多项式 $A(x)$ ,要在模 $x^n$ 意义下求 $B(x)$ ,使得 $B(x)\equiv \ln (A(x))\ (\mbox{mod}\ x^n)$ .
两边同时求导,得到 $B’(x)\equiv \frac {A’(x)} {A(x)}\ (\mbox{mod}\ x^n)$ .
多项式求逆得到 $\frac 1 {A(x)}$ ,再算出 $B’(x)$ ,再对 $B’(x)$ 不定积分得到 $B(x)$ .
这里 $B(x)$ 的常数项是 $0$ ,因为 $a_0=1$ ,若将 $\ln$ 函数大力展开,就可以发现 $B$ 的常数项就是 $\ln a_0$ .
时间复杂度 $\Theta(n\log n)$ .
多项式牛顿迭代
已知一个函数 $G(x)$ ,在模 $x^n$ 意义下求一个多项式 $F(x)\ \mbox{mod}\ x^n$ ,使得 $G(F(x))\equiv 0(\mbox{mod}\ x^n)$ .
仍然将项数用 $0$ 补到 $2$ 的幂次.当 $n=1$ 时,需要单独求解 $G(F(x))\equiv 0(\mbox{mod}\ x)$ .
否则,先求解 $F_0(x)$ ,使得 $G(F_0(x))\equiv 0 (\mbox{mod}\ x^{\frac n 2})$ .
考虑如何拓展到模 $x^n$ 下,把 $G(F(x))$ 在 $F_0(x)$ 处进行泰勒展开,
$$
G(F(x))=G(F_0(x))+\frac{G’(F_0(x))}{1!}\cdot (F(x)-F_0(x))+\frac{G’’(F_0(x))}{2!}\cdot (F(x)-F_0(x))^2 + \dots
$$
因为 $G(F(x))\equiv 0(\mbox{mod}\ x^n)$ ,所以 $G(F(x))\equiv 0(\mbox{mod}\ x^{\frac n 2})$ 也成立.
而 $G(F_0(x))\equiv 0 (\mbox{mod}\ x^{\frac n 2})$ 所以 $F(x)$ 与 $F_0(x)$ 次数低于 $x^{\frac n 2}$ 的部分是相同的.
所以展开式中从第三项 $\frac{G’’(F_0(x))}{2!}\cdot (F(x)-F_0(x))^2$ 起,在模 $x^n$ 意义下都为 $0$ .于是只保留前两项,得到
$$
G(F(x))\equiv G(F_0(x))+{G’(F_0(x))}\cdot (F(x)-F_0(x))\ (\mbox{mod}\ x^n)
$$
而 $G(F(x))\equiv 0(\mbox{mod}\ x^n)$ ,所以就有
$$
F(x)\equiv F_0(x)-\frac {G(F_0(x))} {G’(F_0(x))}\ (\mbox{mod}\ x^n)
$$
需要注意,这里的 $G’(F_0(x))$ 是以 $F_0(x)$ 作为自变量求导,而不是以 $x$ 作为自变量求导.
如,若 $G(x)=\ln x,F_0(x)=x$ ,则 $G’(F_0(x))=\frac 1 {F_0(x)}=\frac 1 x$ ,而不是 $\ln(1)=0$ .
时间复杂度为 $O(n\log n)$ ,由于可以实现类似解方程的操作,所以用途比较广泛.
如实现多项式开根,就可以直接设 $G(x)=x^2-A$ .
Luogu P4726 多项式 $\exp$
给定项数为 $n$ 的多项式 $A(x)$ ,在 $\mbox{mod} \ x^n$ 意义下求多项式 $B(x)$ ,使得 $B(x)\equiv \exp(A(x))\ (\mbox{mod} \ x^n)$ .
取对数,得到 $\ln B\equiv A \ (\mbox{mod} \ x^n)$ ,令 $G(x)=\ln x-A$ .
则问题等价于求解 $F(x)$ ,使得 $G(F(x))\equiv 0(\mbox{mod}\ x^n)$ .
直接套用牛顿迭代的那一套理论,得到
$$
F\equiv (1-{\ln (F_0)+A})\cdot F_0\ (\mbox{mod}\ x^n)
$$
递归求解,当 $n=1$ 时,令 $F_0(x)=\exp a_0$ 即可.一般会保证多项式 $A$ 的常数项 $a_0=0$ .
Luogu P5245 多项式快速幂
给定项数为 $n$ 的多项式 $A(x)$ ,正整数 $k$ .
在 $\mbox{mod}\ x^n$ 下求多项式 $B(x)$ ,使得 $B(x)\equiv A^k(x)\ (\mbox{mod} \ x^n)$ .
两边同时取对数,得到 $\ln B(x)\equiv k\ln A(x) \pmod {x^n}$ ,可以看出 $k$ 可以直接对 $P$ 取模.
再对两边同时做一次 $\exp$ ,得到 $B(x)\equiv \exp(k\ln A(x)) \pmod {x^n}$ .
Luogu P5050 多项式多点求值
给定一个 $n$ 次多项式 $F(x)$ 和 $m$ 个数 $a_i$ ,需要求出每个 $F(a_i)$ 的值.
定义减法卷积 ${\rm MULT}(F(x),G(x))=\sum_{i\ge0}(\sum_{j\ge 0}f_{i+j}g_j)x^i$ ,可以将一个多项式取反后再卷积来实现.
有 $F(a_i)=[x^0]{\rm MULT}(F(x),\frac{1}{1-a_ix})$ ,且 ${\rm MULT}(F(x),G(x)H(x))={\rm MULT}({\rm MULT}(F(x),G(x)),H(x))$ .
分治地来求每个 $F(a_i)$ .
$$
G(l,r,x):={\rm MULT}(F(x),\frac 1{\prod_{i=l}^r(1-a_ix)}) \bmod x^{r-l+1}\\
G(l,mid,x)={\rm MULT}(G(l,r,x),\prod_{i=mid+1}^r (1-a_ix))\bmod x^{mid-l+1}\\
G(mid+1,r,x)={\rm MULT}(G(l,r,x),\prod_{i=l}^{mid} (1-a_ix)) \bmod x^{r-mid}
$$
当递归到 $l=r$ 时,此时的 $G(l,r,x)$ 的常数项就是我们要求的点值了.
每个要用到的 $\prod_{i=l}^r (1-a_ix)$ 可以用分治 NTT 预处理出来,时间复杂度 $O(n\log^2 n)$ .
Loj 150 挑战多项式
给出次数为 $n$ 的多项式 $F(x)$ ,求
$$
\displaystyle G(x) \equiv \left({\left({1+\ln\left({2+F(x)-F(0)-{\exp\left({\int_0^x\frac{1}{\sqrt{F(t)}}\textrm{d}t}\right)}}\right)}\right)^k}\right)^\prime \pmod {x^n}
$$
在代码里面把多项式除法/取模也加上了.
1 | //%std |