多项式
多项式操作
模板
1 |
|
O(n^2) 模板
1 |
|
任意模数模板
三模NTT
1 | const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3; |
MTT
1 |
|
多项式乘法
多项式平移
定义：对于一个多项式 $F(x)$，求 $G(x)\equiv F(x+c)(\bmod x^n)$，其中 $c$ 为常数
做法：不妨令 $F(x)=\sum_{i=0}^n f_ix^i$
容易发现是一个差卷积的形式
1 | Poly Offset(const Poly &a, int c) { |
多项式乘法逆
定义：对于一个多项式 $F(x)$，如果存在一个多项式 $G(x)$ 满足 $deg(G)\le deg(A)$，且 $F(x)G(x)\equiv 1(\bmod x^n)$，则称 $G(x)$ 为 $F(x)$ 在模 $x^n$ 意义下的逆元
做法：假设我们现在已经有了 $F(x)G(x)\equiv 1(\bmod x^n)$，我们考虑求出 $F(x)G(x)\equiv 1(\bmod x^{2n})$
我们移项得到 $F(x)G(x)-1\equiv 0(\bmod x^n)$，然后我们考虑平方可以得到 $(F(x)G(x)-1)^2\equiv 0(\bmod x^{2n}$，展开有 $F(x)(2G(x)-F(x)G^2(x))\equiv 1(\bmod x^{2n})$ 一路倍增即可，时间复杂度为 $T(n)=T(\frac n 2)+O(n\log n)=O(n\log n)$
1 | Poly Inv(const Poly &a) { |
多项式牛顿迭代
定义：已知多项式 $F(x)$，求 $G(x)$，满足 $F(G(x))\equiv 0(\bmod x^n)$
做法：我们仍考虑倍增的做法，不妨假设我们现在已经有一个 $G_{k-1}(x)$，满足 $F(G_{k-1}(x))\equiv 0(\bmod x^{2^{k-1}})$，现在我们要求 $G_k(x)$，我们将 $F(G_k(x))$ 在 $G_{k-1}(x)$ 处展开，得到 $F(G_k(x))=\sum_{i=0}^\infty\frac{F^{(i)}(G_{k-1}(x))}{i!}(G_{k}(x)-G_{k-1}(x))^i$
注意到在模 $2^k$ 下，$i$ 大于等于 $2$ 的 $(G_k(x)-G_{k-1}(x))^i$ 都是 $0$，那么就能得到 $G_k(x)=G_{k-1}(x)-\frac{F(G_{k-1}(x))}{F’(G_{k-1}(x))}$
多项式对数函数
定义：多项式对数函数，我们认为是一个多项式和麦克劳林级数的复合，即对于多项式 $F(x)=\sum_{i=1}^{\infty}a_ix^i$，有 $\ln(1-F(x))=-\sum_{i=0}^{\infty}\frac{F^i(x)}{i}$
已知多项式 $F(x)$，如果存在一个多项式 $G(x)\equiv \ln F(x)(\bmod x^n)$，则称 $G(x)$ 为多项式 $F(x)$ 的对数，保证 $f_0=1$
做法：我们对于原式两边求导 $G’(x)\equiv \frac{F’(x)}{F(x)}(\bmod x^n)$，直接求逆即可
1 | Poly Ln(const Poly &a) { |
多项式指数函数
定义：已知多项式 $F(x)$，求 $G(x)$，满足 $e^{F(x)}\equiv G(x)(\bmod x^n)$，保证 $f_0=0$
做法：我们对两边取 $\ln$，得到 $\ln G(x)-F(x)\equiv 0$，套用牛顿迭代的式子，即令 $H(G(x))=\ln G(x)-F(x)$，得到$G_k(x)\equiv G_{k-1}(x)(1-\ln G_{k-1}(x)+F(x))$，时间复杂度 $O(n\log n)$
1 | Poly Exp(const Poly &a) { |
多项式开根
定义：已知多项式 $F(x)$，求 $G(x)$，满足 $F(x)\equiv G^2(x)(\bmod x^n)$，如果 $f_0\neq 1$，需要用二次剩余来求解 $g_0$
做法：我们移项后直接套用牛顿迭代即可，$H(G(x))=G^2(x)-F(x)$，得到 $G_k(x)\equiv \frac{1}{2}(G_{k-1}(x)-\frac{F(x)}{G_{k-1}(x)})$，时间复杂度 $O(n\log n)$
1 | Poly Sqrt(const Poly &a) { // a[0] = 1 |
多项式快速幂
定义：已知多项式 $F(x)$ 和非负整数 $k$，求 $G(x)$，满足 $F^k(x)\equiv G(x)(\bmod x^n)$
做法：两边取 $\ln$ 之后再 $\exp$，得到 $G(x)\equiv \exp(k\ln F(x))$，如果 $f_0$ 等于 $1$，那么我们这样已经做完了，如果 $f_0>1$，那么我们考虑将整体除掉 $f_0$，化为 $f_0=1$ 的情况，如果 $f_0=0$，那么我们需要找一个 $t$，那么 $f_t>0$，且 $f_0$ 到 $f_{t-1}$ 都是 $0$，然后除掉 $f_tx^t$ 再做快速幂即可，细节较多，常数较大，时间复杂度 $O(n\log n)$
1 | Poly Pow(const Poly &a, int k) { // a[0] = 1 |
多项式带余除法
定义：已知一个 $n$ 次多项式 $F(x)$ 和一个 $m(m\le n)$ 次多项式 $G(x)$，要求出一个 $n-m+1$ 次多项式 $Q(x)$ 和一个次数小于 $m$ 的多项式 $R(x)$，满足 $F(x)=Q(x)G(x)+R(x)$
做法：感觉已经超脱了多项式的领域
我们带入 $\frac{1}{x}$ 得：$F(\frac{1}{x})=Q(\frac 1 x)G(\frac 1 x)+R(\frac 1 x)$，两边同乘 $x^{n-1}$ 得：$x^{n-1}F(\frac 1 x)=x^{n-m}Q(\frac 1x)x^{m-1}G(\frac 1x)+x^nR(\frac 1x)$
我们令 $F^{R}(x)$ 表示将 $F(x)$ 的系数翻转，那么之前的式子等价于 $F^R(x)=Q^R(x)G^R(x)+x^{n-m+1}R^R(x)$
那么 $F^R(x)\equiv Q^R(x)G^R(x)(\bmod x^{n-m+1})$，那么 $Q^R(x)$ 就是求个逆元的问题，求出 $Q(x)$ 之后减一下就能得到 $R(x)$ 了，时间复杂度 $O(n\log n)$
1 | pair<Poly, Poly> Divide(const Poly &a, const Poly &b) { |
多项式经典结论
多项式的幂次
拉格朗日插值
$n$ 个点可唯一确定一个 $n-1$ 次多项式，而拉格朗日差值就是用来根据这 $n$ 个点来确定这个多项式的算法
推导过程
我们令
容易得到当且仅当我们带入点 $(x_k,y_k)$，$f_k(x)$ 才能等于 $y_k$，其它情况均等于 $0$
那么可以得到这个多项式 $f(x)=\sum_{i=1}^{n}f_i(x)$，这个式子不是太好看，我们稍微提一下公共项
令 $l(x)=\prod_{i=1}^{n}(x-x_i)$，$\omega_k=\frac{y_k}{\prod_{i\neq k}(x_k-x_i)}$，那么 $f(x)=l(x)\sum_{i=1}^{n}\frac{\omega_i}{(x-x_i)}$
模板
对于任意给定的 $n+1$ 个点，我们可以做到 $O(n^2)$ 求系数和求值
1 | void Lagrange(int *res, int *x, int *y, int n) { |
动态加点可以做单次 $O(n)$ 求值和系数
如果 $x_i$ 连续，可以做到一次 $O(n)$ 求值