多项式 - 空白菌

多项式基础

数域的定义

定义 复数集的子集 K ，满足 0,1∈K 且元素的和差积商（除数不为 0 ）都属于 K ，那么称 K 是一个数域。

关于群环域的详细定义可以看看抽代，这里只提及必须知道的。

例如有理数集、复数集、模素数 m 剩余系都是数域，但整数集不是数域。

多项式的定义与基本性质

定义 设 a0,a1,⋯,an 是数域 K 上的数，其中 n 为非负整数，那么称 f(x)=n∑i=0aixi 是数域 K 上的一元多项式，其中 aixi 是 f(x) 的 i 次项，ai 则是 f(x) 的 i 次项系数。

此外，也可以用 [xi]f(x) 表示多项式 f(x) 的 i 次项系数。

注意，这里的 x 是形式上的记号，而非真正的数。换句话说，单独写出系数序列也能代表一个多项式， x 的次数更多时候只是用来区分系数。

一元多项式环的定义 数域 K 上多项式的全体，称为一元多项式环，记作 K[x] ，而 K 称为 K[x] 的系数域。

次数的定义 对于多项式 f(x) ，其系数非零的最高次项的次数称为多项式的次数，记作 ∂(f(x)) 。

相等的定义 若两个多项式对应次数的各系数均相等，那么这两个多项式相等。

零多项式的定义 系数全为 0 的多项式，记为 0 ，其次数不考虑。

多项式加法的定义 对于两个多项式 f(x)=n∑i=0aixi,g(x)=m∑i=0bixi ，则 f(x)+g(x)=max(n,m)∑i=0(ai+bi)xi 。

多项式乘法的定义 对于两个多项式 f(x)=n∑i=0aixi,g(x)=m∑i=0bixi ，则 f(x)⋅g(x)=n∑i=0m∑j=0aibjxi+j 。

多项式乘法有一个等价形式，f(x)⋅g(x)=n+m∑k=0xkk∑i=0aibk−i ，即求两个多项式系数的加法卷积（下标之和相等的位置的值的乘积之和），这是今后许多问题可以转化为多项式计算的关键。

多项式复合的定义 对于两个多项式 f(x)=n∑i=0aixi,g(x)=m∑i=0bixi ，则 f(g(x))=a0+n∑i=1aigi(x) 。

性质1 数域 K 上的两个多项式经过加、减、乘等运算后，所得结果仍然是数域 K 上的多项式。

性质2 对于两个多项式 f(x),g(x) ，满足加法结合律、加法交换律、乘法结合律、乘法交换律、乘法对加法分配律、乘法消去律。

性质3 任意 n+1 个不同的采样点，就可以唯一确定一个 n 次多项式。

多项式带余式除法

定理1（带余式除法） 在一元多项式环 K[x] 中，任意两个多项式 A(x),B(x) 且 B(x)≠0 ，一定存在唯一的两个多项式 Q(x),R(x) 满足 A(x)=Q(x)B(x)+R(x) ，其中 ∂(R(x))<∂(B(x)) 或 R(x)=0 ，称 Q(x) 为 A(x) 除以 B(x) 的商， R(x) 为 A(x) 除以 B(x) 的余式。

大部分数论整除同余的性质都可以类似地应用到多项式上，后面就不展开了。

形式幂级数的定义

定义 设 a0,a1,⋯,an 是数域 K 上的数，那么称 f(x)=∞∑i=0aixi 是数域 K 上的形式幂级数，简称幂级数。

形式幂级数环的定义 数域 K 上形式幂级数的全体，称为形式幂级数环，记作 K[[x]] 。

幂级数可以看作是一元多项式的扩展，其具有更多良好的性质，如形式导数和形式不定积分等。

在模意义下，幂级数可等价为有限项的多项式，因此通常会把多项式扩展到幂级数上，借由幂级数的诸多性质得到许多有用的结论，例如模意义下多项式的初等函数。

幂级数的导数和不定积分

注意，极限在环上可能并不存在，但依然可以在形式上的定义导数与积分。

形式导数 设形式幂级数 f(x)=∞∑i=0aixi ，其形式导数 f′(x)=∞∑i=1iaixi−1 。

此外，我们也可将 f(x) 的 t 阶导数记作 f(t)(x) 。

形式不定积分 设形式幂级数 f(x)=∞∑i=0aixi ，其形式不定积分 ∫f(x)dx=∞∑i=1iaixi−1+C 。

其他的基本求导法则皆可适用，就不再展开了。

常见幂级数展开

多项式插值

多项式插值的定义

定义 给定 n 个点 (x1,y1),⋯,(xn,yn) ，其中 xi 互不相同，求这些点确定的 n−1 次多项式函数 f(x) 的过程，称为多项式插值。

多项式插值的方法

拉格朗日插值法

考虑构造 n 个辅助函数 gi(x)=yi∏j≠ix−xjxi−xj ，显然 gi(x) 满足 gi(xi)=yi 且 gi(xj)=0,j≠i 。

因此我们令 f(x)=n∑i=1gi(x)=n∑i=1yi∏j≠ix−xjxi−xj 即可唯一确定所求多项式，此为拉格朗日插值公式。

其中，若 xi=i ，可以预处理阶乘以及 x−xj 的前后缀积，将公式化简为 O(n) 。

若我们只需要求出在 x = k 处的值，那么代入即可。

若要求出具体的系数则设计多项式运算的模拟。

这里只给出求单点值的代码。

时间复杂度 O(n^2)

空间复杂度 O(n)

重心拉格朗日插值法

若插值点会新增 q 次，每次重新计算 f(k) 都是 O(n^2) ，我们需要对公式做些调整。

\displaystyle f(x) = \sum_{i = 1}^n y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j} = \prod_{i=1}^n (x - x_i) \sum_{i = 1}^n \frac{y_i}{(x-x_i)\prod_{j \neq i} (x_i-x_j)} 。

我们设 \displaystyle A = \prod_{i=1}^n (x - x_i) , B(i)=\displaystyle \prod_{j \neq i} (x_i-x_j) 。

每次新增插值点时 O(1) 更新 A ， O(n) 更新 B(i) 后，即可在 O(n) 内得到新的 \displaystyle f(k) = A \sum_{i = 1}^n \frac{y_i}{(k-x_i)B(i)} 。

代码可借鉴的拉格朗日插值法做修改，这里就不给出了。

时间复杂度 O(n^2 + qn)

空间复杂度 O(n)

加法卷积的定义

定义 对于两个序列 f,g ，它们的加法卷积序列 h 满足 \displaystyle h_k = \sum_{i + j = k} f_ig_j 。

把序列当作多项式系数理解， h 其实就是 f,g 表示的多项式的乘积的系数，因此可以用加法卷积的算法加速多项式乘积，下面也会用多项式的角度介绍加法卷积的算法。

加法卷积的变换

快速傅里叶变换（FFT）

多项式在系数域直接加法卷积是 O(n^2) 的，但如果我们在若干个不同位置取两个多项式的点值（采样点），容易发现这些点值相乘后得到的新点值就落在所求的多项式上，最后只要把点值变换回系数，就得到目标多项式。

换句话说，系数域的加法卷积可以变换为点值域的对应相乘，而对应相乘这个过程是 O(n) 的，现在我们只需要一个能够快速在系数域和点值域之间变换算法即可。

这也是大多数变换加速卷积的核心思路，即找到一个快速的可逆变换，使得两个序列变换后的对应位置做运算的结果，恰好为两个序列卷积的变换，最后逆变换回去就是两个序列的卷积。

接下来就是加法卷积的需要的变换，离散傅里叶变换。

离散傅里叶变换（DFT）

首先，点值域的点不能随便取，我们要取 n 次单位根 \omega_n 的 n 个幂 \omega_n^0, \omega_n^1, \cdots, \omega_n^{n-1} ，n 要大于等于多项式的项数。为了方便，我们通常需要令 n 为 2 的幂。

n 次单位根等价于将复平面单位圆弧划分为 n 等分，其中第 k 份即 \omega_n^k = \cos \dfrac{2k\pi}{n} + \text{i}\sin \dfrac{2k\pi}{n} 。

单位根具有许多有用的性质：

1. 互异性：若 i \neq j ，则 \omega_n^i \neq \omega_n^j 。
2. 折半律：\omega_{2n}^{2i} = \omega_{n}^{i} 。
3. 周期律：\omega_n^{i + n} = \omega_n^i 。
4. 半周期律： \omega_n^{i + \frac{n}{2}} = -\omega_n^i 。

互异性保证了 n 个点一定互不相同，接下来考虑如何求值。

设 \displaystyle f(x) = \sum_{i = 0}^{n-1} a_i x^i ，那么显然有 f(x) = a_0 + a_2x^2 + \cdots + a_{n-1}x^{n-1} + x(a_1 + a_3x^2 + \cdots + a_nx^n) 。

设 f_1(x) = a_0 + a_2x + \cdots a_{n-1}x^{n-1} ,f_2(x) = a_1 + a_3x + \cdots + a_nx^n ，那么有 f(x) = f_1(x^2) + xf_2(x^2) 。

当 i \in [0, \dfrac{n}{2} - 1] 时，我们代入单位根 \omega_n^i 可得

我们代入单位根 \omega_n^{i + \frac{n}{2}} 可得

注意到 f_1(\omega_{\frac{n}{2}}^{i}) 和 f_2(\omega_{\frac{n}{2}}^{i}) 正是子问题的答案。

因此一个大小为 n 的问题，变成两个大小为 \dfrac{n}{2} 的子问题外加 O(n) 复杂度计算，递归下去总体复杂度是 O(n\log n) 的。（如果随便取点，问题规模不会折半，也就不能快速了）

于是，多项式系数域到点值域的快速正变换就找到了。

位逆序置换

递归的常数较大，我们希望改为迭代，考虑 2^3 项多项式的变换过程：

1. 初始层：\{a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7\} 。
2. 第一层：\{a_0, a_2, a_4, a_6\},\{a_1, a_3, a_5, a_7\} 。
3. 第二层：\{a_0, a_4\},\{a_2, a_6\},\{a_1, a_5\}, \{a_3, a_7\} 。
4. 第三层：\{a_0\}, \{a_4\},\{a_2\}, \{a_6\},\{a_1\}, \{a_5\}, \{a_3\}, \{a_7\} 。

我们需要从下往上迭代，那么就需要知道最后一层的顺序。

容易知道，a_i 最后会出现在 a_{rev_i} ，其中 rev_i 表示 i 的二进制逆序，例如 110 的逆序就是 011 。

根据 rev 的定义，我们可以递推它在 n 项多项式的情况：

因此，我们预处理 rev 后，将对应系数置换即可迭代。

蝶形运算优化

在上面，当我们求出 f_1(x) 和 f_2(x) 的各 \dfrac{n}{2} 个点值后，设 i \in [0, \dfrac{n}{2}-1] ，那么

注意到 f(\omega_n^i) 和 f(\omega_n^{i + \frac{n}{2}}) 分别在 i 和 i + \frac{n}{2} 位置上，而 f_1(\omega_{\frac{n}{2}}^{i}) 和 f_2(\omega_{\frac{n}{2}}^{i}) 也恰好在 i 和 i + \frac{n}{2} 位置上，因此我们不需要额外空间，只需要原地覆盖即可。

离散傅里叶逆变换（IDFT）

现在，我们尝试推导一下逆变换。

我们定义点值多项式 \displaystyle F(x) = \sum_{i = 0}^{n-1} f(\omega_n^{i})x^i ，即 f(x) 点值当作系数的多项式。

我们代入 x = \omega_n^k ，那么 \displaystyle F(\omega_n^k) = \sum_{i = 0}^{n-1} \omega_n^{ik}\sum_{j = 0}^{n-1} a_j\omega_n^{ij} = \sum_{j = 0}^{n-1} a_j\sum_{i = 0}^{n-1} \omega_n^{i(k+j)} 。

构造辅助多项式 \displaystyle G(x) = \sum_{i = 0}^{n-1} x^i ，那么 \displaystyle F(\omega_n^k) = \sum_{j=0}^{n-1}a_jG(\omega_n^{j+k}) 。

考虑 G(\omega_n^i) ，当 i = 0 时 G(\omega_n^i) = n ，否则单位根两两配对 G(\omega_n^i) = 0 。

因此 F(\omega_n^k) = na_{n-k} ，特别地当 k = 0 时 F(\omega_n^0) = na_0 ，所以我们只需要对点值多项式进行一次DFT，随后将 [1,n-1] 项反转，最后对所有项除以 n 即可还原多项式。

时间复杂度 O(n \log n)

空间复杂度 O(n)

快速数论变换（NTT）

考虑在素域内的多项式变换，我们发现原根刚好能代替单位根。

考虑一个素数 P ，表达为 P = r \cdot 2^k + 1 ，其原根 G 的阶为 \varphi(P) = P-1 = r \cdot 2^k ，当多项式含有 n = 2^{k'} 项时，我们令 G_n = G^{\frac{P-1}{n}} 那么 G_n 等价为 n 次单位根。

注意到，一个素数能支持的多项式长度为 2^k ，因此 k 越大越好，不过常见的 10^9 + 7 就比较鸡肋，因为 k = 1 。

NTT其他部分和FTT完全一致。

时间复杂度 O(n \log n)

空间复杂度 O(n)

常用NTT模数：

任意模数NTT（MTT）

暂时不学。

多项式初等函数

多项式牛顿迭代

给定多项式 g(x) ，求 f(x) ，满足 g(f(x)) \equiv 0 \pmod{x^n} 。

考虑倍增法。

当 n = 1 时， [x^0]g(f(x)) = 0 需要单独解出。

假设在模 x^{\left\lceil \frac{n}{2} \right\rceil} 时的 f(x) 的解是 f_0(x) ，那么我们对 g(f(x)) 在 f_0(x) 处泰勒展开有

显然，当 i \geq 2 时， (f(x) - f_0(x))^i \equiv 0 \pmod{x^n} ，因此有

最后化简得

这就是模意义下的牛顿迭代，每次都能倍增多项式有效系数，一些关键多项式初等函数需要由此推导。

模 x^n 是因为精确解实际上大概率是幂级数，但大部分时候我们的操作只需要前几项，就能保证覆盖所有有意义的部分，因此幂级数是不必要的，求出模意义下的就够了。

多项式求逆

给定多项式 f(x) ，求 f^{-1}(x) ，满足 f(x)f^{-1}(x) \equiv 1 \pmod{x^n} 。

设 g(f^{-1}(x)) = \dfrac{1}{f^{-1}(x)} - f(x) \equiv 0 \pmod{x^n} 。

当 n = 1 时，[x^0]f^{-1}(x) = ([x^0]f(x))^{-1} ，因此需要保证常数项逆元存在。

假设模 x^{\left\lceil \frac{n}{2} \right\rceil} 的解为 f_0(x) 。

根据牛顿迭代

因此，我们可以用这个公式迭代出多项式的逆，复杂度由主定理 T(n) = T(n/2) + O(n \log n) = O(n \log n) 。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式除法&取模

给定多项式 f(x),g(x) ，求 q(x),r(x) ，满足 f(x) = q(x)g(x) + r(x) 。

其中 \partial(q(x)) = \partial(f(x)) - \partial(g(x)), \partial(r(x)) < \partial(g(x)) 。

设 n = \partial(f(x)), m = \partial(g(x)) ，不妨设 \partial(r(x)) = m-1。

因为存在余式，我们不能直接使用模 x^m 的多项式求逆。

设 f_R(x) = x^nf\left( \dfrac{1}{x} \right) ，其实就是将系数反转。

我们对原式变形

有 \partial(q_R(x)) = \partial(q(x)) = n-m < n-m+1 ，因此在模 x^{n-m+1} 下 q_R(x) 是不会被影响的，而 x^{n-m+1}r_R(x) 会被模掉。

所以有 f_R(x) \cdot g^{-1}_R(x) \equiv q_R(x) \pmod{x^{n-m+1}} 。

求出 q_R(x) 后，反转系数就是 q(x) ，最后 r(x) = f(x) - q(x)g(x) 。

实现上注意处理除式的后导 0 ，会导致结果出错，虽然一般题目不需要这个处理。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式开方

给定多项式 f(x) ，求 \sqrt{f(x)} \bmod x^n 。

设 g(\sqrt{f(x)}) = \left( \sqrt{f(x)} \right)^2 - f(x) \equiv 0 \pmod {x^n} 。

当 n = 1 时， [x^0]\sqrt{f(x)} = \sqrt{[x^0]f(x)} ，因此需要保证常数项二次剩余存在。

假设模 x^{\left\lceil \frac{n}{2} \right\rceil} 的解为 f_0(x) 。

根据牛顿迭代

代码没实现求二次剩余，目前只能对常数项为 1 的开方。

特别地，出现前导 0 时，前导 0 个数 cnt 是偶数（即第一个非零项是偶次）则多项式可以整体除以 x^{cnt} 再开方，最后乘 x^{cnt/2} ，否则无解。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式对数函数

给定多项式 f(x) ，求 \ln f(x) \bmod x^n 。

求导再积分后， \displaystyle \ln f(x) \equiv \int \frac{f'(x)}{f(x)} \text{d}x \pmod {x^n} 。

注意根据 \ln 的定义， f(x) 的常数项必须为 1 ，否则对数无意义。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式指数函数

给定多项式 f(x) ，求 e^{f(x)} \bmod x^n 。

设 g(e^{f(x)}) = \ln e^{f(x)} - f(x) \equiv 0 \pmod{x^n} 。

当 n = 1 时，[x^0]e^{f(x)} = e^{[x^0]f(x)} ，因此需要保证常数项为 0 ，否则无意义。

假设模 x^{\left\lceil \frac{n}{2} \right\rceil} 的解为 f_0(x) 。

根据牛顿迭代

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式幂函数

给定多项式 f(x) ，求 f^k(x) \bmod x^n 。

显然有 f^k(x) \equiv e^{k \ln f(x)} \pmod{x^n} 。

指数并非真正的指数，而是多项式函数的自变量，因此指数上的 k 也是对 P 取模。

当 [x^0]f(x) \neq 1 时，我们找到第一个非零项 [x^{cnt}]f(x) ，多项式可以整体除以 [x^{cnt}]f(x) \cdot x^{cnt} 再用上面的公式，最后乘 ([x^{cnt}]f(x))^k \cdot x^{k \cdot cnt} ，其中 [x^{cnt}]f(x) 的 k 次方要模 \varphi(P) ，因为他是真正意义的指数。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式三角函数

给定多项式 f(x) ，求 \sin f(x) \bmod x^n 和 \cos f(x) \bmod x^n 。

考虑欧拉公式 e^{\text{i}\theta} = \cos \theta + \text{i} \sin \theta 。

因此有 \sin \theta = \dfrac{e^{\text{i} \theta} - e^{-\text{i} \theta}}{2 \text{i}} , \cos \theta = \dfrac{e^{\text{i} \theta} + e^{-\text{i} \theta}}{2} 。

令 \theta = f(x) 即可，其中 \text{i} 在模 P 下等价于 g^{\frac{P-1}{4}} ，注意 f(x) 常数项必须为 0 ，否则无意义。

此外，用这两个函数可以推导出其他三角函数（但有些无法在 0 处展开，且在其他位置展开都存在超越数，就不存在于这个模多项式体系了），这里就不一一列举了。

时间复杂度 O(n \log n)

空间复杂度 O(n)

多项式反三角函数

给定多项式 f(x) ，求 \arcsin f(x) \bmod x^n 和 \arctan f(x) \bmod x^n 。

考虑求导再积分回去， \displaystyle \arcsin f(x) = \int \frac{f'(x)}{\sqrt{1 - f^2(x)}} \text{d}x, \arctan f(x) = \int \frac{f'(x)}{1 + f^2(x)} \text{d}x 。

为什么没有 \arccos ？因为他的多项式常数是超越数，在这个体系无意义。上面能求的积分出来的常数是 0 。

时间复杂度 O(n \log n)

空间复杂度 O(n)

位运算卷积

位运算卷积的定义

快速沃尔什变换（FWT）

子集卷积的定义

快速莫比乌斯变换（FMT）

多项式分治

多项式多点求值

多项式快速插值

分治加法卷积

多项式线性齐次递推

多项式平移