多项式学习笔记

多项式基本表现形式

$\mathbf A(x) = \sum a_i x^i$A(x)=∑ai​xi

多项式乘法

$\begin{aligned} \mathbf A(x) &= \sum a_i x^i\\ \mathbf B(x) &= \sum b_i x^i\\ \mathbf C(x) &= \mathbf A(x) \times \mathbf B(x)\\ &= \sum_{i = 0}^{n - 1} a_i \cdot x^i \sum_{j = 1}^{n - 1} b_j \cdot x^j\\ &= \sum_{i = 0}^{2n - 2} c_i \cdot x^i \end{aligned}$A(x)B(x)C(x)​=∑ai​xi=∑bi​xi=A(x)×B(x)=i=0∑n−1​ai​⋅xij=1∑n−1​bj​⋅xj=i=0∑2n−2​ci​⋅xi​

其中

$\begin{aligned} c_i = \sum_{j = 0}^{i} a_j \cdot b_{i - j} \end{aligned}$ci​=j=0∑i​aj​⋅bi−j​​

多项式的表达方法

• 系数表达

对于$\mathbf A(x) = \sum a_i \cdot x^i$A(x)=∑ai​⋅xi，其系数表达就是由多项式系数组成的向量$a = (a_0, a_1, \dots, a_{n - 1})$a=(a0​,a1​,…,an−1​)

用系数计算多项式乘法复杂度为$O(n^2)$O(n2)

• 点值表达

对于$\mathbf A(x) = \sum a_i x^i$A(x)=∑ai​xi，其点值表达是由$n$n个点值组成的集合

$\{(x_0, y_0), (x_1, y_1), \dots (x_{n - 1}, y_{n - 1})\}${(x0​,y0​),(x1​,y1​),…(xn−1​,yn−1​)}

其中

$\forall i\not = j, x_i\not = x_j$∀i​=j,xi​​=xj​

对于计算$\mathbf A(x) \times \mathbf B(x)$A(x)×B(x)，我们将表示$\mathbf A(x)$A(x)和$\mathbf B(x)$B(x)的点值口占，使每个多项式包含$2n$2n个点值对

$\{(x_0, y_0), (x_1, y_1), \dots, (x_{2n - 1}, y_{2n - 1})\}\\ \{(x_0, y'_0), (x_1, y'_1), \dots, (x_{2n - 1}, y'_{2n - 1})\}\\ \{(x_0, y_0y'_0), (x_1, y_1y'_1), \dots, (x_{2n - 1}, y_{2n - 1}y'_{2n - 1})\}${(x0​,y0​),(x1​,y1​),…,(x2n−1​,y2n−1​)}{(x0​,y0′​),(x1​,y1′​),…,(x2n−1​,y2n−1′​)}{(x0​,y0​y0′​),(x1​,y1​y1′​),…,(x2n−1​,y2n−1​y2n−1′​)}

拉格朗日插值

$\mathbf A(x) = \sum_{k = 0}^{n - 1} \frac{\prod_{j\not = k}x - x_j}{\prod_{j\not = k}x_k - x_j}$A(x)=k=0∑n−1​∏j​=k​xk​−xj​∏j​=k​x−xj​​

本原单位根

满足$x^n - 1 = 0$xn−1=0的$x$x被称作$n$n次单位根

如果我们有一个$\omega$ω，对于$\omega^0, \omega^1, \dots, \omega^{n - 1}$ω0,ω1,…,ωn−1互不相同，就称$\omega$ω为本原单位根，我们用$\omega_n$ωn​表示为一个$n$n次本原单位根，且它们均匀地分布在以复平面的原点为圆心的单位半径的圆周上

其中

$\omega_n^0 = \omega_n^n = 1, \omega_n^{n / 2} = -1$ωn0​=ωnn​=1,ωnn/2​=−1

利用复数的指数形式定义

$e^{iu} = cos(u) + i sin(u)$eiu=cos(u)+isin(u)

引理

$\omega_n^j \omega_n^k = \omega_n^{j + k} = \omega_n^{(j + k)\bmod n}\\ \forall n \ge 0, k \ge 0, d > 0, \omega_{dn}^{dk} = \omega_n^k\\ \forall n > 0, n \bmod 2 = 0, \omega_n^{n / 2} = w_2 = -1$ωnj​ωnk​=ωnj+k​=ωn(j+k)modn​∀n≥0,k≥0,d>0,ωdndk​=ωnk​∀n>0,nmod2=0,ωnn/2​=w2​=−1

DFT

将多项式的系数表示转变为点值表示，设$\mathbf a$a是长度为$n$n的序列，对于$0\leq k<n$0≤k<n，令

$b_k = \sum_{i = 0}^{n - 1} a_i \cdot \omega_n^{ki}$bk​=i=0∑n−1​ai​⋅ωnki​

则称$\mathbf b$b为$\mathbf a$a的离散傅里叶变换DFT，记作$\mathbf b=\mathbf {DFT}(\mathbf a)$b=DFT(a)

IDFT

将多项式的点值表示转变为系数表示，DFT的逆变换

从$\mathbf b$b得到$\mathbf a$a，我们有公式

$a_k = \frac{1}{n} \sum_{i = 0}^{n - 1} b_i \cdot \omega_n^{-ki}$ak​=n1​i=0∑n−1​bi​⋅ωn−ki​

证明，将上面两个式子结合

$\begin{aligned} \frac{1}{n} \sum_{i = 0}^{n - 1} b_i \cdot \omega_n^{-ki} &= \frac{1}{n} \sum_{i = 0}^{n - 1}\omega_n^{-ki} \sum_{j = 0}^{n - 1} a_j \cdot \omega_n^{ij}\\ &= \frac{1}{n} \sum_{i = 0}^{n - 1} a_i \sum_{j = 0}^{n - 1}\omega_n^{-ki} \cdot \omega_n^{ij}\\ &= \frac{1}{n} \sum_{i = 0}^{n - 1} a_i \sum_{j = 0}^{n - 1}\omega_n^{i(j - k)} \end{aligned}$n1​i=0∑n−1​bi​⋅ωn−ki​​=n1​i=0∑n−1​ωn−ki​j=0∑n−1​aj​⋅ωnij​=n1​i=0∑n−1​ai​j=0∑n−1​ωn−ki​⋅ωnij​=n1​i=0∑n−1​ai​j=0∑n−1​ωni(j−k)​​

对于$j = k$j=k，有

$\sum_{j = 0}^{n - 1} \omega_n^{i(j - k)} = n$j=0∑n−1​ωni(j−k)​=n

对于$j\not = k$j​=k，因为$0 \leq j,k < n$0≤j,k<n，所以$0 < |j - k| < n$0<∣j−k∣<n，所以$\omega_n^{j - k} \not = 1$ωnj−k​​=1 ，根据等比数列求和公式得到

$\begin{aligned} \sum_{j = 0}^{n - 1} \omega_n^{i(j - k)} &= \sum_{j = 0}^{n - 1} (\omega_n^{j - k})^i\\ &= \frac{1 - (\omega_n^{j - k})^n}{1 - \omega^{j - k}}\\ &= \frac{1 - (\omega_n^n)^{j - k}}{1-\omega^{j - k}}\\ &= 0 \end{aligned}$j=0∑n−1​ωni(j−k)​​=j=0∑n−1​(ωnj−k​)i=1−ωj−k1−(ωnj−k​)n​=1−ωj−k1−(ωnn​)j−k​=0​

于是考虑原式

$\frac{1}{n} \sum_{i = 0}^{n - 1} b_i \sum_{j = 0}^{n - 1}\omega_n^{i(j - k)} = a_i$n1​i=0∑n−1​bi​j=0∑n−1​ωni(j−k)​=ai​

蝴蝶操作

时间复杂度为$O(n \log n)$O(nlogn)

设$n = 2m$n=2m，我们有一个这样的变换

$\begin{aligned} \mathbf A(x) &= \mathbf {A_0}(x^2) + x\mathbf {A_1}(x^2)\\ \mathbf {A_0}(x) &= \sum_{i = 0}^{m - 1} a_{2i} \cdot \omega_n^i\\ \mathbf {A_1}(x) &= \sum_{i = 0}^{m - 1} a_{2i + 1} \cdot \omega_n^i \end{aligned}$A(x)A0​(x)A1​(x)​=A0​(x2)+xA1​(x2)=i=0∑m−1​a2i​⋅ωni​=i=0∑m−1​a2i+1​⋅ωni​​

对于$0 \leq k < n$0≤k<n，$x = \omega_n^k$x=ωnk​

$\begin{aligned} \mathbf A(\omega_n^k) &= \mathbf A_0(\omega_m^k) + \omega_n^k \mathbf A_1(\omega_m^k)\\ \mathbf A(\omega_n^{k + m}) &= \mathbf A_0(\omega_m^k) - \omega_n^k\mathbf A_1(\omega_m^k) \end{aligned}$A(ωnk​)A(ωnk+m​)​=A0​(ωmk​)+ωnk​A1​(ωmk​)=A0​(ωmk​)−ωnk​A1​(ωmk​)​

这两个结果只有常数项不同，那么可以同时计算两个式子的结果

位逆序置换

我们可以发现，如果每次都对奇偶分离的话，最终我们要处理的顺序，是对于顺序排列的二进制反着输出一遍的结果

for (int i = 0; i < maxn; i++) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1);
}

我们把序列$\mathbf a$a按$\mathbf {rev}$rev的值的顺序排序得到$\mathbf a'$a′

FFT实现

设$maxn$maxn是第一个大于等于$n$n且是$2$2的整次幂的数

我们对$\mathbf a'$a′中每一对相邻的长度为$2^k$2k的序列进行蝴蝶操作，其中$1 \leq 2^k < maxn$1≤2k<maxn，就实现了FFT

观察DFT和DFT的逆变换的式子

$\begin{aligned} b_k &= \sum_{i = 0}^{n - 1} a_i \cdot \omega_n^{ki}\\ a_k &= \frac{1}{n} \sum_{i = 0}^{n - 1} b_i \cdot \omega_n^{-ki} \end{aligned}$bk​ak​​=i=0∑n−1​ai​⋅ωnki​=n1​i=0∑n−1​bi​⋅ωn−ki​​

不同点仅两处常数，所以对于FFT和IFFT我们带个参数，实现方法就一致了

void init() {
    for (int i = 1; i < maxn; i <<= 1) {
        for (int j = 0; j < i; j++) {
            w[i + j] = (node){cos(pi * j / i), sin(pi * j / i)};
        }
    }
}
void fft(node *a, int opt) {
    for (int i = 0; i < maxn; i++) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int i = 1; i < maxn; i <<= 1) {
        for (int j = 0; j < maxn; j += i << 1) {
            for (int k = 0; k < i; k++) {
                node x = a[j + k], t = (node){w[i + k].x, w[i + k].y * opt} * a[i + j + k];
                a[j + k] = x + t;
                a[i + j + k] = x - t;
            }
        }
    }
}

考虑核心部分的复杂度，长度为$2^k$2k的序列共有$\log n$logn种，我们当作$\log n$logn层，每一层我们要计算$n/2$n/2次，总的复杂度就是$O(n \log n)$O(nlogn)

原根

$g$g为$p$p的原根，当且仅当$g^k,0 \leq k \leq p-2$gk,0≤k≤p−2在$\mod p$modp意义下均不相同

当$p$p是质数时，原根一定存在

在$\mod p$modp意义下，$g$g可以说是一个$p - 1$p−1次本原单位根

数论变换 NTT

考虑到FFT有精度问题，但我们可以通过利用原根的不同次方实现FFT，我们可以把FFT过程中的$\omega_n^k$ωnk​替换为$g_n^k$gnk​并不断取模

因为$g_n^k$gnk​对于$0 \leq k < n$0≤k<n有不同的取值，所以上述方案是可行的，也就是$g$g在$\mod p$modp意义下有本原单位根的性质

重点在于这个模数，我们必须选一个质数$p$p，$p - 1$p−1要含有$2$2的幂的因子，并且这个$2$2的幂要大于多项式系数个数$n$n，通常选择形如$a\cdot 2^k + 1$a⋅2k+1的素数

常见的模数有UOJ模数

$998244353 = 7 \times 17 \times 2^{23} + 1$998244353=7×17×223+1

还有

$1004535809 = 479 \times 2^{21} + 1$1004535809=479×221+1

上面两个数的最小正原根都是$3$3