「Note」2023-01-16 Poly Whole Family Bucket

被薄纱，但是感觉很妙。

$\mathtt{Problem}$

定义多项式 $A(x) = \sum_{i = 0}^{n - 1} a_i x^i$ 和 $B(x) = \sum_{i = 0}^{n - 1} b_i x^i$ 相乘的结果为 $C(x)$ 。
即 $C(x) = A(x) \times B(x) = \sum_{k=0}^{n + m - 2} x_k \sum_{i + j = k} a_i b_j$ 。
复杂度为 $\Theta(n^2)$ ，考虑如何更快计算。

---

$\mathtt{FFT \ Editorial}$

$n$ 次方是 $1$ 的复数被称作 $n$ 次单位根。 放在复平面上，这 $n$ 个向量都在单位圆上，终点构成了正 $n$ 边形的 $n$ 个顶点。把其中最小正幅角所对应的向量记为 $\omega_n$ ，那么根据复数乘法可知，另外的 $n - 1$ 个向量分别是 $\omega_n^2, \omega_n^3, \dotsb , \omega_n^n$ ，其中 $\omega_n^n = \omega_n^0 = 1$ 。可以根据其几何特征得到 $\omega_{n}^{k} = \cos k \frac{2\pi}{n} + i \sin k \frac{2\pi}{n}$ ，由此可以推出后面推导中的性质。 首先探讨什么是傅里叶变换，简单地就是把 $\omega_n^k$ 依次代入多项式，作为 $x$ 的值，接下来叙述这个变换的意义。 设 $(b_0, b_1, \dotsb ,b_{n - 1})$ 是多项式 $A(x) = \sum_{i = 0}^{n - 1} a_i x^i$ 的傅里叶变换（$b_i$ 即为 $w_n^i$ 代入多项式后的值），然后以这个变换得到的 $b$ 作为系数再次定义一个多项式 $B(c) = \sum_{i = 0}^{n - 1} b_i x^i$ ，把 $\omega_n$ 的倒数作为 $x$ 带进去，得到一个新的傅里叶变换 $c_0, c_1, \dotsb, c_{n - 1}$。 $$ \begin{aligned} c_k &= \sum_{i = 0}^{n - 1} b_i (w_n^{-k})^i \\ &= \sum_{i = 0}^{n - 1} (\sum_{j = 0}^{n - 1} a_j (w_n^i)^j) (w_n^{-k})^i \\ &= \sum_{j = 0}^{n - 1} a_j (\sum_{i = 0}^{n - 1} (w_n^{j - k})^i)\\ \end{aligned} $$

拿出来 $\sum_{i = 0}^{n - 1} (w_n^{j - k})^i$ ，观察发现在 $j \not = k$ 时，这个式子用等比数列求出来是 $0$ ，而在 $j = k$ 是这个式子为 $n$ ，所以最后得到 $a_i = \frac{c_i}{n}$。

那么这两次傅里叶变换操作的结果是：系数 - 点值 - 系数 。

---

现在开始正题，既然已经实现了 系数 - 点值 - 系数 的变化，那么我们的相乘可以在两个多项式都变成了 点值 的时候进行，这个直接是相同项的点值对应相乘即可，为线性的操作。

那么瓶颈就变成傅里叶变换操作是 $\Theta(n^2)$ 的，需要更优。

快速傅里叶变换 的思想是基于 分治。因为所有的值都需要带进去一次，这一层 $\Theta(n)$ 没办法优化掉，那么现在的目标是更快地计算 $A(\omega_{n}^{k}) = \sum_{i = 0}^{n - 1} a_i \omega_{n}^{k}$ 。

考虑按幂的奇偶分组
$$ A(x) = a_0 x^0 + a_2 x^2 + \dotsb + a_{n - 2} x^{n - 2} + a_1 x^1 + a_3 x^3 + \dotsb + a_{n - 1} x^{n - 1} $$
再定义两个多项式
$$A_0(x) = a_0 x^0 + a_2 x^2 + \dotsb + a_{n - 2} x^{\frac{n}{2} - 2}, A_1(x) = a_1 x^{1 - 1} + a_3 x^{3 - 1} + \dotsb + a_{n - 1} x^{\frac{n}{2} - 1 - 1}$$
那么 $A(x) = A_0(x^2) + xA_1(x^2)$ 。

现在拿到 $A(\omega_n^k) = A_0(\omega_n^{2k}) + \omega_n^k A_1(\omega_n^{2k})$ ，已知偶数次单位根有性质 $\omega_{n}^i = -\omega_{n}^{i + n / 2}$ （旋转半圈，符号相反），且 $A_0$ 和 $A_1$ 均为偶函数。

那么有

$$ \begin{aligned} A(\omega_n^k) &= A_0(\omega_{n/2}^k) + \omega_{n}^k \times A_1(\omega_{n / 2}^k) \\ A(\omega_n^{k + \frac{n}{2}}) &= A_0(\omega_{n/2}^k) - \omega_{n}^k \times A_1(\omega_{n / 2}^k) \end{aligned} $$

于是便可以在 $\Theta(n \log n)$ 的复杂度内求解了。

$\mathtt{NTT \ Editorial}$

当需要取模的时候，FFT 便无法解决，这里引入 NTT （数论变换），但是依然有局限性。
FFT 妙的地方在于两次变换的相互转换，这源于单位根的比较好的性质。此处引入原根 。

首先归纳一下单位根的性质。

• $\omega_n^k = (\omega_n^1)^k$ 源自定义
• $\omega_n^{0 \sim n - 1}$ 互不相同
• $\omega_n^k = \omega_n^{k \mod n}$
• $\omega_n^{k + n / 2} = -\omega_n^k$
• $\omega_{2n}^{2k} = \omega_n^k$

再看原根，对于质数 $p$ ，其模意义同余系 $F_p$ 恰好能从 $1$ 到 $p - 1$ 取遍，如果有一个数 $g$ ，使 $g$ 的界能达到 $p$ 的上界，则 $g$ 是 $p$ 的原根。

但是原根本身作不了单位根，拥有和单位根一样性质的是 $g^{(p - 1) / n}$ ，证明可以依次带进去，不多说。

于是，找到了单位根的替代品，这个就是数论变换。

相关会用到的原根表

$\mathtt{Prime}$	$\mathtt{Primitive Root}$
$1004535809$	$2$
$998244353$	$3$

$\mathtt{Poly \ WFB}$

$\mathtt{Ploy \ INV}$

给定多项式 $f(x)$ ，求 $f^{-1}(x)$ 。
首先对于常数项有
$$ [x^0]f^{-1}(x) = ([x^0]f(x))^{-1} $$
假设已求出 $f(x)$ 在模 $x^{\lfloor \frac{n}{2} \rfloor}$ 意义下的逆元 $f_0^{-1}(x)$ 。那么

$$ \begin{aligned} f(x)f_0^{-1}(x) \equiv 1 & \pmod{x^{\lfloor \frac{n}{2} \rfloor}} \\ f(x)f^{-1}(x) \equiv 1 & \pmod{x^{\lfloor \frac{n}{2} \rfloor}} \\ f^{-1}(x) - f_0^{-1}(x) \equiv 0 & \pmod{x^{\lfloor \frac{n}{2} \rfloor}} \end{aligned} $$

然后对两边平方

$$ f^{-2}\left(x\right)-2f^{-1}\left(x\right)f^{-1}_{0}\left(x\right)+f^{-2}_{0}\left(x\right)\equiv 0 \pmod{x^{n}} $$

两边同乘 $f\left(x\right)$

$$ f^{-1}\left(x\right)\equiv f^{-1}_{0}\left(x\right)\left(2-f\left(x\right)f^{-1}_{0}\left(x\right)\right) \pmod{x^{n}} $$

于是可以倍增计算了。复杂度为 $\Theta(n \log n)$ 。

$\mathtt{Poly \ SQRT}$

给定多项式 $g(x)$ 求 $f(x)$ 使得 $f^2(x) \equiv g(x) \pmod{x^n}$ 。

当 $\left[x^0\right]g(x)$ 不为 $0$ 时。

$$ \left[x^0\right]f(x) = \sqrt{\left[x^0\right]g(x)} $$

若 $\left[x^0\right]g(x)$ 没有平方根，则多项式 $g(x)$ 没有平方根，或者说$\left[x^0\right]g(x)$ 可能有多个平方根，选取不同的根会求出不同的 $f(x)$。

假设现在已经求出了 $g\left(x\right)$ 在模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的平方根 $f_{0}\left(x\right)$，那么

$$ \begin{aligned} f_{0}^{2}\left(x\right)&\equiv g\left(x\right) &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ \left(f_{0}^{2}\left(x\right)-g\left(x\right)\right)^{2}&\equiv 0 &\pmod{x^{n}}\\ \left(\frac{f_{0}^{2}\left(x\right)+g\left(x\right)}{2f_{0}\left(x\right)}\right)^{2}&\equiv g\left(x\right) &\pmod{x^{n}}\\ \frac{f_{0}^{2}\left(x\right)+g\left(x\right)}{2f_{0}\left(x\right)}&\equiv f\left(x\right) &\pmod{x^{n}}\\ 2^{-1}f_{0}\left(x\right)+2^{-1}f_{0}^{-1}\left(x\right)g\left(x\right)&\equiv f\left(x\right) &\pmod{x^{n}} \end{aligned} $$

同样地可以倍增计算。复杂度为 $\Theta(n \log n)$ 。

$\mathtt{Poly \ DIV-MOD}$

给定两个多项式 $f(x), g(x)$ ，求 $g(x)$ 除 $f(x)$ 的商 $Q(x)$ 和余数 $R(x)$ 。

发现在没有余数 $R(x)$ 的情况下，可以直接求逆，问题变成消掉 $R(x)$ 。

构造一个变换 $f^R(x) = x^{\deg f} f(\frac{1}{x})$ ，为方便表示，记 $n = \deg f, m = \deg g$ 。

发现这个变化本质上是把 $f$ 的系数反了一遍。

现在将 $f(x) = Q(x) g(x) + R(x)$ 这个式子的中所有的 $x$ 都替换成 $\frac{1}{x}$ 然后两边同时乘上 $x^n$ 。

$$ x^n f(\frac{1}{x}) = x^nQ(\frac{1}{x})g(\frac{1}{x}) + x^nR(\frac{1}{x}) $$

然后拆一波系数

$$ x^n f(\frac{1}{x}) = x^{n-m}Q(\frac{1}{x})x^mg(\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)$ ，发现$R(x)$ 的系数是 $x^{n - m + 1}$ 。那么在模 $x^{n - m + 1}$ 的意义下可以直接消掉。

因为 $Q(x)$ 的次数小于 $R(x)$ 的系数，所以不受影响。
最后可以得到 $f^R(x) \equiv Q^R(x)g^R(x) \pmod{x^{n - m + 1}}$ 。
求逆后乘起来就可以了，复杂度依然是 $\Theta(n \log n)$ 。

$\mathtt{Newton's \ method}$

$\mathtt{Taylor \ Series}$

先从泰勒展开开始，用不严谨的话来讲泰勒展开就是用低次到高次的多项式累加来拟合函数在某个点邻域的函数值。

我们用 $P(x)$ 来拟合 $f(x)$ 。
从最简单的开始，首先满足值相等，为了使拟合更接近，让这两个函数在 $x_0$ 处的一阶导相等，再来一次，让这两个函数在 $x_0$ 处的二阶导相等，再继续不断拟合。

那么，拟合过程就是让 $P(x)$ 和 $f(x)$ 在前 $m$ 阶导数相等。
就是说 $P^{(n)}(x) = f^{(n)}(x), n=0,1,,2,...,m$ 。
不难得到 $f(x)$ 在 $x_0$ 处泰勒展开的式子是 $P(x) = \sum_{n=0}^{m}\frac{(x - x_0)^n}{n!} f^{(n)}(x_0)$ 。

$\mathtt{Poly \ Newton's \ Method}$

待填坑。