多项式没家桶
多项式
前置
- NTT
- FFT
- 一定的数学
多项式乘法
NTT/FFT即可
毒瘤卡常之预处理原根（然鹅不开O2有可能反向优化，慎用）：
1 |
|
多项式求逆
问题：
对于给定 $F (x)$ ，求出 $G(x)$ 使得 $ G(x)F(x) \equiv 1 \pmod {x^n}$ ，其中 $A(x) \equiv 1 \pmod {x^n}$ 指 $A(x)$ 次数低于 $n$ 的项只有常数为1，其余都为0，即 $A(x) = 1 + 0x + 0x^2 + 0x^3 + … + 0x^{n - 1} + a_nx^n + a_{n + 1}x^{n + 1} + …$
做法：
考虑倍增，变形：
$$
\begin{aligned}
设G_0(x)满足:\\
& G_0(x)F(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
故:\\
& G(x) - G_0(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
& (G(x) - G_0(x))^2 \equiv 0 \pmod {x^n}\\
& G^2(x) - 2G(x)G_0(x) + G_0^2(x) \equiv 0 \pmod {x^n}\\
\because & G(x)F(x) \equiv 1 \pmod {x^n}\\
\therefore & G(x) - 2G_0(x) + G_0^2(x)F(x) \equiv 0 \pmod {x^n}\\
& G(x) \equiv (2 - G_0(x)F(x))G_0(x) \pmod {x^n}
\end{aligned}
$$
注意特判常数项要有逆，然后倍增即可，时间 $O(n \log n)$
1 |
|
多项式除法和取模
问题：
对于给定 $F(x), G(x)$ ，其中 $deg(F) \ge deg(G)$ ，不妨设 $deg(F) = n, deg(G) = m$ ，求 $Q(x), R(x)$ 使得 $F(x) = Q(x)G(x) + R(x)$ ，且 $deg(Q) = n - m, deg(R) = m - 1$ ，其中 $R(x)$ 最高位可以为0
做法：
对于多项式 $A(x)$ ，记 $A_r(x) = x^{deg(A)}A(\frac{1}{x})$ （其实就是把 $A$ 的系数翻转）
变形：
$$
\begin{aligned}
& F(\frac{1}{x}) = Q(\frac{1}{x}) G(\frac{1}{x}) + R(\frac{1}{x})\\
& x^n F(\frac{1}{x}) = x^{n -m} Q(\frac{1}{x}) x^m G(\frac{1}{x}) + x^{n - m + 1} x^{m - 1} R(\frac{1}{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) \pmod {x^{n - m + 1}}\\
& Q_r(x) \equiv F_r(x) G_r^{-1}(x) \pmod {x^{n - m + 1}}
\end{aligned}
$$
多项式求逆得 $G_r^{-1}(x)$ ，多项式乘法得 $Q_r(x)$ ，计算即可得 $Q(x), R(x)$ ，时间还是 $O(n \log n)$
1 |
|
多项式开根
问题：
给定 $F(x)$ ，求 $G(x)$ 满足 $G^2(x) \equiv F(x) \pmod {x^n}$
做法：
当然可以多项式快速幂求 $F^{\frac{1}{2}}(x)$
也可以考虑倍增，变形：
$$
\begin{aligned}
设G_0(x)满足:\\
& G_0^2(x) \equiv F(x) \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
故:\\
& G^2(x) - G_0^2(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
& (G(x) + G_0(x)) (G(x) - G_0(x)) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
& G(x) - G_0(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\\
& G^2(x) - 2G(x)G_0(x) + G_0^2(x) \equiv 0 \pmod {x^n}\\
& F(x) - 2G(x) G_0(x) + G_0^2(x) \equiv 0 \pmod {x^n}\\
& G(x) \equiv \frac{G_0^2(x) + F(x)}{2G_0(x)} \pmod {x^n}
\end{aligned}
$$
边界条件是常数项必须是模 $P$ 的二次剩余，时间 $O(n \log n)$
代码懒得打了，反正次幂也行
牛顿迭代
牛顿是一种思考的方法，多项式的题很多都用倍增，但每一道题都手推式子太过痛苦，于是，我们可以（更痛苦的）推出式子
问题：
对于给定 $F(x)$ ，求 $G(x)$ ，使 $F(G(x)) \equiv 0 \pmod {x^n}$
做法：
推式子（啊啊啊我要疯了）：
呃……突然发现康托展开我不会，推个寂寞，直接给结论：
$$
G(x) \equiv G_0(x) - \frac{F(G_0(x))}{F’(G_0(x))} \pmod {x^n}
$$
多项式求导和积分
来两个简单的，直接算就行了
求导：
1 | for (int i = 1; i < len; ++i) |
积分：
1 | //逆元可以预处理 |
多项式对数
问题：
对于给定 $F(x)$ ，求出 $G(x)$ 使得 $G(x) \equiv \ln(F(x)) \pmod {x^n}$
做法：
求导，有 $G’(x) \equiv \frac{F’(x)}{F(x)} \pmod {x^n}$
多项式求导得 $F’(x)$ ，求逆得 $\frac{1}{F(x)}$ ，乘法得 $G’(x)$ ，积分出 $G(x)$ ，时间 $O(n \log n)$ ，注意要保证常数项 $f_0 = 1$
1 |
|
多项指数
问题：
对于给定 $F(x)$ ，求 $G(x)$ 使得 $G(x) \equiv e^{F(x)} \pmod {x^n}$
做法：
两边取对数得， $\ln(G(x)) \equiv F(x) \pmod {x^n}$
由牛顿迭代：
$$
\begin{aligned}
G(x) \equiv G_0(x) - \frac{\ln(G_0(x)) - F(x)}{\frac{1}{G_0(x)}} \pmod {x^n}\\
G(x) \equiv (1 - \ln(G_0(x)) + F(x)) G_0(x) \pmod {x^n}\\
\end{aligned}
$$
时间 $O(n \log n)$ ，注意一定要有 $f_0 = 0$
1 |
|
多项式次幂
问题：
对于给定 $F(x), k$ ，求 $G(x)$ 使得 $G(x) \equiv F^k(x) \pmod {x^n}$
做法：
推式子：
$$
\begin{aligned}
& G(x) \equiv F^k(x) \pmod {x^n}\\
& \ln(G(x)) \equiv k \ln(F(x)) \pmod {x^n}\\
\end{aligned}
$$
对 $F(x)$ 取 $\ln$ ，乘 $k$ 以后 $\exp$ 即可
但是并不保证常数项为1，则求 $\exp$ 时边界不一定为1了，不能直接取对数，所以提公因式，设 $r$ 为 $F(x)$ 的第一个非0项次数，提取公因式 $a_rx^r$ 就可以保证最低位是1了
考虑提公因式对答案的影响：我们提了公因式后，最后答案的前 $k * r$ 项都为0，后面的项就是我们求出来的，最后一起乘一个 $a_r^m$ 即可
1 |
|
多项式开根2
前置：Cipolla算法
如果 $y^2 \equiv x \pmod P$ ，则称 $x$ 为模 $P$ 的二次剩余（然鹅我们要求的是 $y$ ）
而对于不保证 $f_0 = 0$ 的开根，我们必须要求出 $f_0$ 做 $x$ 时的 $y$
下面是一堆我听不懂的思路
可以找一个 $t$ ，使得 $t^2 - x$ 为非二次剩余，设 $w = t^2 - x$ ，则 $y = (t + \sqrt{w})^{\frac{P + 1}{2}}$ ，这里考虑把 $w$ 定义为负数中的 $i$ ，随机选 $t$ 尝试即可
1 |
|
多项式三角函数
问题：
对于给定 $F(x)$ ，求 $\sin F(x), \cos F(x), \tan F(x)$
做法：
$$
\begin{aligned}
考虑欧拉公式： \\
& e^{i \theta} = \cos \theta + i \sin \theta \\
故: \\
& e^{i x} = \cos x + i \sin x \\
& e^{i (-x)} = \cos (-x) + i \sin (-x) = \cos x - i \sin x \\
所以: \\
& \cos x = \frac{e^{i x} + e^{-i x}}{2} \\
& \sin x = \frac{e^{i x} - e^{-i x}}{2i} \\
待入f(x): \\
& \cos F(x) = \frac{\exp(i F(x)) + \exp(-iF(x))}{2} \\
& \sin F(x) = \frac{\exp(i F(x)) - \exp(-iF(x))}{2i} \\
又因为: \\
& i^2 \equiv -1 \pmod P \\
所以: \\
& i^2 \equiv P - 1 \pmod P
\end{aligned}
$$
做一遍二次剩余求出 $i$ ，照着计算即可
1 |
|
多项式反三角函数
问题：
对于给定 $F(x)$ ，求 $\arcsin F(x), \arccos F(x), \arctan F(x)$
做法：
直接积分得
$$
\begin{aligned}
& \arcsin F(x) =\int \frac{F’(x)}{\sqrt{1 - F^2(x)}} dx \\
& \arccos F(x) = - \int \frac{F’(x)}{\sqrt{1 - F^2(x)}} dx \\
& \arctan F(x) = \int \frac{F’(x)}{1 + F^2(x)} dx \\
\end{aligned}
$$
1 |
|
拉格朗日反演
不造有啥用，给个式子吧：
若两个多项式 $F(x), G(x)$ 满足常数项为0且1次项不为0，且两者互为复合
逆，即 $G(F(x)) = x$ （或者 $F(G(x)) = x$ ，它们是等价的），则有：
$$
\begin{aligned}
[x^n] F(x)
& = \frac{1}{n} [x^{-1}] \frac{1}{G^n(x)} \\
& = \frac{1}{n} [x^{n - 1}] (\frac{x}{G(x)})^n
\end{aligned}
$$
简证：
$$
\begin{aligned}
\sum_{i = 0}^{n - 1} a_i G^i(x) & = x \\
\sum_{i = 0}^{n - 1} a_i i G^{i - 1}(x) G’(x) & = 1 \\
\sum_{i = 0}^{n - 1} a_i i G^{i - n - 1}(x) G’(x) & = \frac{1}{G^n(x)} \\
[x^{-1}] \sum_{i = 0}^{n - 1} a_i i G^{i - n - 1}(x) G’(x) & = [x^{-1}] \frac{1}{G^n(x)} \\
对于 i \ne n : \\
G^{i - n - 1}(x) G’(x) & = \frac{1}{i - n} (G^{i - n}(x))’ \\
求导, x^{-1} 系数为 0, 所以只考虑 i = n : \\
[x^{-1}] G^{-1}(x) G’(x) & = 1 \\
[x^n] F(x) & = \frac{1}{n} [x^{-1}] \frac{1}{G^n(x)} \\
\end{aligned}
$$
封装
由于那么多东西烦的很，于是封装了
千万别打 class 和shit一样，我用的 namespace
1 |
|