多项式浅谈

$J h b 的多项式浅谈$

这个的后半部分似乎可以当做金策大佬论文的人话解读。

推销一下窝的博客 , 本文所有的代码都在窝的博客上。

多项式主要的用途是用来优化式子，因为笔者也刚刚入门多项式，可能谈到的内容也十分浅，有错请直接开 D。

我们从大整数乘法入手，我们经常写的算法是通过枚举两个整数的每一位，通过位权来更新答案，这里显然是 $O (n^{2})$ 。还有一种是分治乘法，还是通过位权，原理是：
$(A x^{m} + B) (C x^{m} + D) = A C x^{2 m} + ((A + B) (C + D) - A C - B D)) x^{m} + B D$
我们直接分治可以算出答案复杂度 $O (n^{2})$ 复杂度比较优秀？其实这种想法和之后的 MTT 优化是相同的。其中 n 表示位数。

复杂度怎么算？ $T (n) = 4 T (\frac{n}{2}) + O (n)$

$T (n) = O (n^{2})$

之后我们考虑优化 $A C x^{m} + ((A - B) (D - C) + A C + B D) \times x^{\frac{n}{2}} + B D$ 这边只有 3 个乘积可以考虑优化 $T (n) = 3 T (\frac{n}{2}) + O (n) = O (n^{\log_{2} 3})$ 可以接受。

主定理：
$T (n) = a T (⌈ \frac{n}{b} ⌉) = O (n^{d}) T (n) = {\begin{cases} O (n^{d}), d > l o g_{b} a O (n^{d} \log n), d = l o g_{b} a O (n^{l o g_{b} a}), d < l o g_{b} a \end{cases}$

但是我们可以我们 FFT 将系数表示法变成点值表示法，从而得到答案复杂度 $O (n \log n)$ 。

我们常用的表示法是系数表示法 $f (x) = \sum_{i = 0} a_{i} x^{i}$ 我们可以从中取 n + 1 个点来表示这个多项式，也就是 $f (x) = a_{0}, a_{1} \dots a_{n}$

DFT 就是把一个多项式从系数转化成点值，IDFT 反之。

FFT

对于两个个点值表示法的多项式 $f (x) = (x_{0}, f (x_{0})) \dots (x_{n}, f (x_{n}))$ 和 $g (x) = (x_{0}, g (x_{0})) \dots (x_{n}, g (x_{n}))$

设 $F (x) = f (x) \cdot g (x) = (x_{0}, f (x_{0}) g (x_{0})) \dots (x_{n}, f (x_{n}) g (x_{n}))$ 可以看出我们能够快速得将其相乘。

但是直接暴力 DFT,IDFT 是 $O (n^{2})$ 的，有些暴力还是用高斯消元。。。

我们发现 $x^{i}$ 在 $x = 1, - 1$ 的时候是很简单的，这会让我们想到圆，之后我们需要 n + 1 个数，那么我们不妨用模长为 1 的复数。

$ω_{n} = e^{\frac{2 π i}{n}}$ 则 $x^{n} = 1$ 的解集为 $ω_{n}^{k} | k = 0, 1 \dots n - 1$ 也就是将一个圆分成 n 等分。

$ω_{n} = e^{\frac{2 π i}{n}} = c o s (\frac{2 π}{n}) + i \cdot s i n (\frac{2 π}{n})$

$单位圆$

在一个复平面上，以原点为圆心，1 为半径作圆，所得到的圆就是单位圆，将其 n 等分（ n 等分点就是终点），形成 n 个向量，设幅角为正且最小的向量 $w_{n}$ ，称为 n 次单位根

剩下的复数为 $w_{n}^{2} \dots w_{n}^{n}$

$w_{n}^{0} = w_{n}^{n} = 1$

$w_{n}^{k} = \cos k \times \frac{2 π}{n} + i \sin k \times \frac{2 π}{n}$

单位根的幅角为周角的 $\frac{1}{n}$

$w_{n}^{\frac{n}{2} + k} = - w_{n}^{k}$

证明考虑将其展开 $w_{n}^{\frac{n}{2}} \times w_{n}^{k}$

将左边的那项展开得到 $- 1$

$(w_{n}^{k})^{2} = w_{\frac{n}{2}}^{k}$

证明考虑，复数相乘，幅角相加，模长为 $1 \times 1 = 1$ 因为都是单位根

$F F T $

首先我们先假设一个多项式的系数 ~~假设 n 为偶数~~ $A (x) = (a_{0}, a_{1}, a_{n - 1})$

$$
A(x)=a_0+a_1x+a_2{x^2}+a_3*{x^3}+a_4*{x^4}+a_5*{x^5}+ \dots+a_{n-2}*x^{n-2}+a_{n-1}*x^{n-1}
$$

我们把它的下标按奇偶性分类
${\begin{cases} A (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i} \\ A_{1} (x) = \sum_{i = 0}^{m - 1} a_{2 i} x^{2 i} \\ A_{2} (x) = \sum_{i = 0}^{m - 1} a_{2 i + 1} x^{2 i + 1} \\ m = \frac{n}{2} \end{cases}$
所以我们可以得到

$A (x) = \sum_{i = 0}^{m - 1} a_{2 i} (x^{2})^{i} + x \sum_{i = 0}^{m - 1} a_{2 i + 1} (x^{2})^{i}$

所以我们可以将其分成两部分进行递归，也就是 $A (x) = A_{1} (x^{2}) + x A_{2} (x^{2})$

但是根据主定理，这是 $O (n^{2})$

我们考虑 $A (w_{n}^{k}) = A_{1} ((w_{n}^{k})^{2}) + w_{n}^{k} A_{1} ((w_{n}^{k})^{2})$

$(w_{n}^{k})^{2} = w_{\frac{n}{2}}^{k}$

所以可以化简
$\begin{aligned} m & = \frac{n}{2} \\ A (w_{n}^{k}) & = A_{1} (w_{m}^{k}) + w_{n}^{k} A_{2} (w_{m}^{k}) \\ 之后来看后半部分 \\ A (w_{n}^{k + m}) & = A_{1} (w_{m}^{k}) - w_{n}^{k} A_{2} (w_{m}^{k}) \end{aligned}$
发现只要知道了 RHS 就可以直接求出，复杂度为 $O (n \log n)$

这叫蝴蝶变换

$I D F F$

这里就只想结论 $B (x) = \sum_{i = 0}^{n - 1} b_{i} \times x^{i}$ 在 $w_{n}^{k i}$

其中 $0 \leq k < n$ 的点值

发现 $w_{n}^{- k}$ 与 $w_{n}^{k}$ 是对应的， $w_{n}^{- k} = w_{n}^{n + k}$

所以我们只要用 FFT 之后再将数组反过来就可以了

递归形式的 FFT

我们发现原来的每一个位置，在结束之后会变成其的反序

具体来说

cpp

1
2
3

原来的序列: 000 001 010 011 100 101 110 111
结束的序列: 000 100 010 110 001 101 011 111
也就是二进制倒了

我们考虑求出最终的位置，之后再倒序回去，因为

cpp

i 和 i / 2 的关系:
i = i >> 1 也就是二进制向左移动 1 位
既然是倒序,所以要向右移动 1 位
之后考虑奇数的情况,最后的一个 1 只要移动到最高位上就行了

$C o d e$

cpp

for(int i = 0; i < lim; ++ i) 
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
    
for(int i = 0; i < lim; ++ i) if(i < rev[i]) 
    swap(A[i], A[rev[i]]);

最后我们考虑蝴蝶操作过程

$m = \frac{n}{2}$ 的所有值已经计算好并且放到 A 中了
$\begin{aligned} A_{1} (w_{m}^{k}) & = A [k], A_{1} (w_{m}^{k}) = A [k + m] \\ \Rightarrow A (w_{m}^{k}) & = A [k] + w_{n}^{k} \times A [k + m] \\ \Rightarrow A (w_{m}^{k + m}) & = A [k] - w_{n}^{k} \times A [k + m] \end{aligned}$
之后我们一层层向上递推就可以了

NTT

我们发现 FFT 的精度其实不是很够，最多处理 $10^{8}$ 的数据。我们考虑用什么东西来代替这个 FFT。这里有一个很好的替代品就是原根。对于质数 $p = q n + 1, n = 2^{m}$ 原根 $g$ 满足 $g^{q n} = 1 (\mod p)$ 所以将 $g_{n}$ 看做 $ω_{n}$ 也是可以的。

常用的模数是：
$p = {\begin{cases} 998244353 = 479 \times 2^{21} + 1, g = 3 \\ 1004535809 = 7 \times 17 \times 2^{23} + 1, g = 3 \\ 469762049 = 7 \times 2^{26} + 1, g = 3 \end{cases}$
因为他们的原根都是 3。(这里的模数都是常在 3% NTT 中使用的)

$g^{q n} = e^{2 π n}$ 我们如果迭代到长度 $l$ 的时候 $ω_{n} = g_{l} = g_{n}^{\frac{n}{l}} = g_{n}^{\frac{p - 1}{l}}$

3 模数 NTT

我们考虑如果模数不支持 NTT 怎么办？我们可以自己定模数，只要保证答案符合（大于）范围即可。

其实很简单，就是用 3 个模数做一遍 NTT 之后 CRT 合并即可，用的就是之前说的模数。

MTT

我们考虑如果模数不支持 NTT 而且还卡常怎么办？~~虽然说 NTT 跑得很快~~，如果码力不行怎么办？用 MTT。

这里其实有点争议，就是 3% NTT 到底算不算 MTT。

本文只介绍一种最简单的，但是最常用的优化。

我们考虑进行 FFT 的时候我们用到了复数。那么我们为什么不把一个多项式的系数拆成几的部分分别进行处理，这样就可以保证精度。

假设我们要求 $P \times Q, P = \sum_{i = 0} p_{i} x^{i}, Q = \sum_{i = 1} q_{i} x^{i}$

我们考虑将系数拆成两部分

$A = P_{i} >> 15, B = P_{i} & (32767)$

$C = Q_{i} >> 15, D = Q_{i} & (32767)$

$P * Q = A C * 2^{30} + (A D + B C) * 2^{15} + B D$

之后我们考虑通过复数来表示，设 $F = A + i B, G = C + i \times D$

这样我们可以先通过 FFT 之后再将其表示成答案的形式，最后在计算。

但是我们发现，需要表示之前的式子需要 $\overset{―}{F}, \overset{―}{G}$

$\overset{―}{F}$ 表示 F 的共轭复数。

那么我们来证明一个东西。我们不妨记 $c o n j (x)$ 表示 x 的共轭复数。

用 $P_{t}$ 表示 P 的 DFT。
$证明：P = A + iB, Q = A - iB 注意这里 P, Q 与之前的不同$

$\begin{aligned} p_{t} (x) = & A (w_{n}^{k}) + i B (w_{n}^{k}) \\ = & \sum_{j = 0}^{n - 1} A_{j} w_{n}^{j k} + i B_{j} w_{n}^{j k} \\ = & \sum_{j = 0} 6 n - 1 (A_{j} + i B_{j}) w_{n}^{j k} \end{aligned}$

之后我们考虑能不能将 Q 用 P 表示出来，我们考虑将 Q 进行展开。
$\begin{aligned} Q_{t} (x) = & A w_{n}^{k} - i B (w_{n}^{k}) \\ = & \sum_{j = 0}^{n - 1} (A_{j} - i B_{j}) w_{n}^{j k} \\ = & \sum_{j = 0}^{n - 1} (A_{j} - i B_{j}) (c o s (\frac{2 π j k}{n}) + i s i n (\frac{2 π j k}{n})) \\ = & \sum_{j = 0}^{n - 1} A_{j} c o s (\frac{2 π j k}{n}) + B_{j} s i n (\frac{2 π j k}{n}) + i (A_{j} s i n (\frac{2 π j k}{n}) - B_{j} c o s (\frac{2 π j k}{n})) \\ = & c o n j (\sum_{j = 0}^{n - 1} A_{j} c o s (\frac{- 2 π j k}{n}) + B_{j} s i n (\frac{- 2 π j k}{n}) - i (A_{j} s i n (\frac{- 2 π j k}{n}) - B_{j} c o s (\frac{- 2 π j k}{n}))) \\ = & c o n j (\sum_{j = 0}^{n - 1} (A_{j} + i B_{j}) \times (c o s (\frac{- 2 π j k}{n}) - i s i n (\frac{- 2 π j k}{n}))) \\ = & c o n j (\sum_{j = 0}^{n - 1} (A_{j} + i B_{j}) (w_{n}^{- j k}) \\ = & c o n j (\sum_{j = 0}^{n - 1} (A_{j} + i B_{j}) (w_{n}^{- j k})) \\ = & c o n j (P_{t} (n - k)) \end{aligned}$
这里有两个细节，我们一开始是将两个式子都展开，之后通过欧拉定理进行展开，猜测两个数是共轭质数。

这里变成共轭的时候，将 cos 部分变成负数。

我们考虑一个更加普通的形式对于一个 $w_{n}^{k}$ 的共轭复数是多少？将 $w_{n}^{k}$ 表示成 $a + i b$ 的形式，其共轭复数容易得到是 $a - i b$ 之后我们考虑在数轴上对应的是多少

[外链图片转存失败，源站可能有防盗链机制，建议将图片保存下来直接上传 (img-pQ3sobeh-1618049627378)(https://z3.ax1x.com/2021/04/10/cabTrq.png)]]

可以发现其在轴上的对应点就是 $w_{n}^{- k}$ 可以理解成，原来是向上数 k 的单位，现在是向下数。

之后将其展开也是同理，可以得到 $w_{n}^{- k} = c o s (\frac{- 2 π k}{n}) + i s i n (\frac{- 2 π k}{n})$

但是我们计算答案的时候可没有负的指数，我们可以用 $n - k$ 来表示 $- k$ 因为圆上总共有 n 个点。

这样我们就证明了 $Q$ 可以由 $P$ 表示出来。

所以我们总共只需要进行 4 次 FFT 就可以得到答案了。

多项式求逆

我们需要求 $F \times Q \equiv 1 (\mod x^{n})$ 中的 $Q$ 。

考虑使用递归解决，假设我们已经得到 $Q_{1} \times F \equiv 1 (\mod x^{\frac{n}{2}})$

我们需要求 $F \times Q \equiv 1 (\mod x^{n})$

可以得到 $F \times Q \equiv 1 (\mod x^{\frac{n}{2}})$

考虑将两个式子进行相减来消除 1
$F \times (Q - Q_{1}) \equiv 0 (\mod x^{\frac{n}{2}})$
因为 $F$ 肯定不是 0，所以考虑将其消掉，之后再考虑平方。
$(Q - Q_{1})^{2} \equiv 0 (\mod x^{n}) Q^{2} + Q_{1}^{2} - 2 Q Q_{1} \equiv 0 (\mod x^{n}) Q + F Q_{1}^{2} - 2 Q_{1} \equiv 0 (\mod x^{n}), 这里两边乘了 F Q \equiv 2 Q_{1} - F Q_{1}^{2} (\mod x^{n})$
这样递归去做就可以了。

多项式 Ln

需要求 $Q \equiv \ln F (\mod x^{n})$

我们考虑直接进行 exp ~~发现我们还没学过~~

那么能消去 Ln 的还有什么呢？求导！

$Q^{'} \equiv \frac{F^{'}}{F} (\mod x^{n})$

之后又手就行。

多项式 Exp

需要求 $Q \equiv e^{F} (\mod x^{n})$

我们优先考虑 Ln 转换成 $\ln Q \equiv F (\mod x^{n})$ 之后考虑进行牛顿迭代。
$\begin{aligned} y & = f (x_{0}) + f^{'} (x_{0}) (x - x_{0}) \\ 0 & = f (x_{0}) + f^{'} (x_{0}) (x - x_{0}) \\ 0 & = f (x_{0}) - f^{'} (x_{0}) x_{0} + f^{'} (x_{0}) \\ x & = \frac{f^{'} (x_{0}) x_{0} - f (x_{0})}{f^{'} (x_{0})} \\ x & = x_{0} - \frac{f (x_{0})}{f^{'} (x_{0})} \end{aligned}$
我们考虑将之前的式子变换得到 $\ln Q - F \equiv 0$

我们设函数 $S (G) = \ln G - F$

然后考虑带入之前的式子

这里说明一下 $S^{'} (G) = \frac{1}{G}$ 的原因，我们本质上是将整个 G 看成一个变量，而不是里面的每一个 $x^{i}$ 所以这里并不是符合函数求导。
$G = G_{0} - \frac{\ln G_{0} - F}{\frac{1}{G_{0}}} G = G_{0} - G_{0} \times (\ln G_{0} - F) G = G_{0} \times (1 - \ln G_{0} + F)$
之后有手就行。

多项式开根

我们需要求 $F^{2} = G$ 还是考虑递归，假设 $F_{1}^{2} \equiv G (\mod x^{\frac{n}{2}})$

还是考虑消元
$F \equiv F_{1} (\mod x^{\frac{n}{2}}) F - F_{1} \equiv 0 (\mod x^{\frac{n}{2}}) F^{2} + F_{1}^{2} - 2 F F_{1} \equiv 0 (\mod x^{n}) G F_{1}^{2} - 2 F_{1} F \equiv 0 (\mod x^{n}) F \equiv \frac{G}{2 F_{1} + F_{1}^{2}} (\mod x^{n})$
还是很简单。

多项式除法

给定多项式 $F, G$ 求出多项式 $R, Q$ 使得 $F = G \times Q + R$ 。

其中 $F$ 的次数为 $n, G$ 的次数为 $m$ 。

可以想到如果没有余数的话，我们直接用多项式求逆就可以水掉。

因为这是个多项式，我们考虑将 R 给消掉，然后就可以与愉快得求逆了。

考虑构造 4 个多项式，满足 $F_{1} = G_{1} \times Q_{1} + x^{k} R_{1}$ 这样子只要 $\mod x^{k}$ 就可以得到答案了。考虑构造这个多项式，为了让外面有 $x^{k}$ 这个系数，所以考虑将 $F (x)$ 变成 $F (\frac{1}{x})$ 。可以知道变成这样之后的式子仍然是满足的，我们考虑两边同时乘以 $x^{n}$ 。

$x^{n} F (\frac{1}{x}) = x^{n} G \times Q + x^{n} R$ 我们考虑 $x^{n} F (\frac{1}{x})$ 的每一个系数其实等价于将原来的 F 给翻转一下的系数。那么我们不妨让 $F_{1} = x^{n} F (\frac{1}{n}), Q_{1} = x^{m} Q (\frac{1}{n})$ 其他同理。

那么我们得到 $F_{1} = G_{1} \times Q_{1} + x^{n - m + 1} R_{1}$ 看出 $k = n - m + 1$ 。之后发现一个神奇的事情 $Q_{1}$ 的次数是 $n - m$ 所以我们即使 $\mod x^{n - m + 1}$ 也不会影响 $Q_{1}$ 。所以我们得到式子 $F_{1} (x) = G_{1} (x) \times Q_{1} (x) \mod x^{n - m + 1}$ 也就是 $Q_{1} (x) = \frac{F_{1} (x)}{G_{1} (x)}$ 。

之后我们求出了 $G_{1}$ 之后将其翻转一下就变成 $G$ 了，然后就可以得到 $R (x) = F (x) - G (x) \times Q (x)$ 。

很简单。

这边之后还会更新。