§ 1 多项式基本操作
- 多项式乘法
- 多项式求逆
- 多项式除法/取模
- 多项式开根
- 多项式 $\ln$
- 多项式 $\exp$
- 多项式 $k$ 次幂
为简化运算,所有操作均在 ${\rm mod}\ 998244353$ 意义下进行。实现时注意清空高次系数。
代码中出现的常量、变量及函数定义如下:
1 | typedef long long ll; |
§ 1.1 多项式乘法
直接 $\rm NTT$ 求卷积。
时间复杂度 $O(n\log n)$。
1 | inline void init(const int &n){ |
§ 1.2 多项式求逆
给定多项式 $A(x)$,求 $A^{-1}(x)$ 满足
其中 ${\rm mod}\ x^n$ 表示保留 $0\sim n-1$ 次项。
当 $n=1$ 时,直接用费马小定理得 $a^{-1}\equiv a^{p-2}\pmod{p}$。
当 $n\gt 1$ 时,假设当前已求出 ${\rm mod}\ x^{\lceil\frac{n}{2}\rceil}$ 意义下的 $A(x)$ 的逆元 $B_0(x)$,即
需要求出 $B(x)$ 满足
两式相减得
考虑到 $A(x)\not\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}$,故有
两边平方,考虑卷积定义,可知同余式右边仍为 $0$,即
两边同乘 $A(x)$ 得
化简得
递归求解即可,时间复杂度为 $T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$。
1 | inline vector<int> polyinv(const vector<int> &a, int n = -1){ |
§ 1.3 多项式除法/取模
给定 $n-1$ 次多项式 $A(x)$ 和 $m-1$ 次多项式 $B(x)$,求多项式 $D(x),\ R(x)$ 满足
其中 $D(x)$ 为 $n-m$ 次,$R(x)$ 至多 $m-2$ 次。
由于该式的余数 $R(x)$ 难以处理,考虑去除其影响。
定义 $A(x)$ 的系数反转多项式 $A^R(x)$ 为
则有
所以可在 ${\rm mod}\ x^{n-m+1}$ 意义下求逆得到 $D^R(x)$,反转即为 $D(x)$,然后代入原式计算 $R(x)$。
共需要一次求逆和两次乘法,时间复杂度为 $O(n\log n)$。
1 | inline void polydiv(const vector<int> &a, const vector<int> &b, vector<int> &d, vector<int> &r){ |
§ 1.π 多项式牛顿迭代法
该方法可以用来推很多公式,如多项式求逆、开根以及 $\exp$ 等。
给出一个关于多项式 $f(x)$ 的方程 $g(f(x))=0$,假设已求出 $f(x)$ 的前 $n$ 项 $f_0(x)$,即
将函数 $g(f(x))$ 在 $f_0(x)$ 上泰勒展开得
注意到 $f(x)-f_0(x)$ 第 $0\sim n-1$ 项为 $0$,故 $(f(x)-f_0(x))^2$ 第 $0\sim 2n-1$ 项为 $0$,于是有
化简得
运用一次该公式即可将 $f(x)$ 的已知项数翻倍。
§ 1.4 多项式开根
给定多项式 $A(x)$,求 $B(x)=\sqrt{A(x)}$ 满足
令 $B(x)\equiv B_0(x)\pmod{x^n}$,直接运用牛顿迭代法得
若 $A(x)$ 的常数项不够优秀,递归到边界时还需用 ${\rm Cipolla}$ 算法计算二次剩余,见 T 老师的博文。
时间复杂度为 $T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$。
1 | inline Pair pmul(const Pair &a, const Pair &b, int t){ |
§ 1.5 多项式 $\ln$
给定多项式 $A(x)$,求
考虑直接计算
其中求导和积分都可以在 $O(n)$ 的时间内完成。
代码中省略了预处理逆元的步骤,故积分的复杂度为 $O(n\log n)$。
注意需要保证 $A(x)$ 常数项为 $1$,且默认 $\ln A(x)$ 的常数项为 $0$。
共需要一次求逆,时间复杂度为 $O(n\log n)$。
1 | inline vector<int> polyderiv(const vector<int> &a){ |
§ 1.6 多项式 $\exp$
给定多项式 $A(x)$,求
令 $B(x)=e^{A(x)}\pmod{x^n}$,两边取对数得
然后令 $B(x)\equiv B_0(x)\pmod{x^n}$,运用牛顿迭代法得
注意需要保证 $A(x)$ 常数项为 $0$,且默认 $e^{A(x)}$ 的常数项为 $1$。
时间复杂度为 $T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$。
1 | inline vector<int> polyexp(const vector<int> &a, int n = -1){ |
§ 1.7 多项式 $k$ 次幂
给定多项式 $A(x)$ 和正整数 $k$,求
直接快速幂,时间复杂度为 $O(n\log n\log k)$。
当 $f(x)$ 的常数项为 $1$ 时,有
时间复杂度为 $O(n\log n)$。
当 $f(x)$ 的常数项不为 $1$ 时,设 $f(x)$ 的最低次项为 $ax^d$,则将其提出
可以平移幂次处理后用上面的公式计算,时间复杂度为 $O(n\log n)$。
代码只给出 $f(x)$ 常数项为 $1$ 的情况。
1 | inline vector<int> polypow(const vector<int> &a, const int &ex){ |
§ 2 模板题
=> LibreOJ #150 挑战多项式
§ 2.1 题意
给定一个 $n+1$ 次多项式 $F(x)$ 和一个正整数 $k$,求多项式 $G(x)$ 满足
保证 $F(x)$ 的常数项是 ${\rm mod}\ 998244353$ 的二次剩余。
注意到开根时 $\pm\sqrt{F(x)}$ 均为合法解,只需取常数项较小者计算即可。
所有运算在 ${\rm mod}\ 998244353$ 下进行。
$1\leq n\leq 10^5,\ \ 0\leq k\lt 998244353$。
§ 2.2 代码
1 |
|