多项式学习

Hardsoft

2026-05-22

学习记录

$$ \def\w{\omega} \def\hf{\hat{f}} \def\L{\mathbb{L}} \def\R{\mathbb{R}} \def\F{\mathbb{F}} \def\r#1{{\color{red}#1}} \def\g#1{{\color{green}#1}} $$

一、基本概念

有离散函数 $f_t$，定义域是 $\mathbb{N}$，值域是 $\mathbb{C}$．

可以构造它的普通生成函数/多项式：$\F(x)=\sum\limits_{t=0} f_t x^t$．

二、离散傅立叶变换

在离散傅立叶变换中，离散函数皆采用循环表示法，即 $f_t \gets \sum\limits_{k=0} f_{t+kN}$ 且默认了 $t\in[0,N)$ 和 $N=2^n$．

假设我们现在已经有了信号函数 $f_t$，想要求其频率统计/点值表达 $\hf_s$，有定义：
$$ \hf_s = \F(\w_N^{-s}) = \sum_{t=0} e^{-i \frac{2 \pi}{N} st} f_t $$ 其中的 $\w_N$ 即为 $N$ 次单位根，可以表示为 $\cos(\frac{2\pi}{N}s) + \sin(\frac{2\pi}{N}s)i$．

通过频率统计形式，我们可以轻松对两个信号函数做加法卷积：$$h_t = \sum_{t_1+t_2=t} f_{t_1} g_{t_2} \implies H(x) = F(x) G(x) \implies \hat{h}_s =\hf_s \hat{g}_s$$

轻松得到 $\hat{h}_s$ 之后我们还需要一个逆变换反推到 $h_t$．有结论：

$$ f_t = \frac{1}{N}\hat{\F}(\w_N^t) = \sum_{s=0} e^{i \frac{2\pi}{N} ts} \hf_s$$

证明

考虑我们刚刚究竟做了什么．我们建立了一种信号$\iff$频率的关系．这种关系来自于取单位根的若干次幂带入生成函数求得的点值表达．那么，我们尝试使用矩阵刻画这种关系．
为了方便描述，下文的 $\w = -\w_N$．

$$ \begin{bmatrix} \w^0 & \w^1 & \w^2 & \cdots & \w^{N-1} \\ \w^0 & \w^2 & \w^4 & \cdots & \w^{N-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \w^0 & \w^{N-1} & \w^{N-2} & \cdots & \w^1 \end{bmatrix} \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \end{bmatrix} = \begin{bmatrix} \hf_0 \\ \hf_1 \\ \vdots \\ \hf_{N-1} \end{bmatrix} $$

现在考虑反推，从 $\hf$ 到 $f$．直观思路是把左边的转移系数移到右边去．那么考虑求它的逆元．

$$ \frac{1}{N} \begin{bmatrix} \w^0 & \w^{N-1} & \w^{N-2} & \cdots & \w^{1} \\ \w^0 & \w^{N-2} & \w^{N-4} & \cdots & \w^{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \w^0 & \w^{1} & \w^{2} & \cdots & \w^{N-1} \end{bmatrix} \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \end{bmatrix} = \begin{bmatrix} \hf_0 \\ \hf_1 \\ \vdots \\ \hf_{N-1} \end{bmatrix} $$

尝试写出形式化的两个转移矩阵的系数：$A_{i,j} = \w^{ij}, A^{-1}_{i,j} = \frac{1}{N}\w^{-ij}$．计算 $A \cdot A^{-1} = E$，得到：

$$ \begin{aligned} E_{i,j} &= \sum_{k=0}^{N-1} A_{i,k} A^{-1}_{k,j} \\ &= \sum_{k=0}^{N-1} \frac{1}{N} \w^{ik} \w^{-kj} \\ &= \frac{1}{N} \sum_{k=0}^{N-1} \w^{k(i-j)} = \begin{cases} \displaystyle \frac{1}{N} \w^{i-j} \sum_{k=0}^{N-1}\w^k &= 0 \qquad\text{if}\;i \ne j \\ \displaystyle \frac{1}{N} \w^0 \sum_{k=0}^{N-1}\w^0 &= 1 \qquad\text{if}\;i = j \end{cases} \end{aligned} $$

那么就证毕了．

~~什么？你问我怎么想到这两个转移矩阵的？A: 我也不知道qwq…~~

快速傅立叶变换

考虑加速刚刚所说的变换的计算．目标：$\mathcal O(n \log n)$．

设想，将多项式“分裂”为 $\F(x) = \F_\L(x^2) + x\F_\R(x^2)$，其中 $\F_\L = \sum\limits_{t=0}^{\frac{N}{2}-1} f_{2t}x^t, \F_\R = \sum\limits_{t=0}^{\frac{N}{2}-1} f_{2t+1}x^t$．

这样，我们就有了
$$ \begin{aligned} \hf_s &= \F_\L(\w_N^{-2s}) + \w_N^{-s} \F_\R(\w_N^{-2s}) \\ &= \F_\L(\w_{\frac{N}{2}}^{-s}) + \w_N^{-s} \F_\R(\w_{\frac{N}{2}}^{-s}) \\ &= {\hf_\L}_s + \w_N^{-s} {\hf_\R}_s \end{aligned} \qquad \begin{aligned} \hf_{s+\frac{N}{2}} &= \F_\L(\w_N^{-2s-N}) + \w_N^{-s-\frac{N}{2}} \F_\R(\w_N^{-2s-N}) \\ &= \F_\L(\w_{\frac{N}{2}}^{-s}) - \w_N^{-s} \F_\R(\w_{\frac{N}{2}}^{-s}) \\ &= {\hf_\L}_s - \w_N^{-s} {\hf_\R}_s \end{aligned} $$

也就是说，我们求出来了 ${\hf_\L}_s, {\hf_\R}_s$ 之后，立刻就可以求出来 $\hf_s, \hf_{s+\frac{N}{2}}$．如此分治下去，会得到一个边界条件：$ \hf_s = f_0 $．这样我们就在 $\mathcal O(n \log n)$ 时间内变换了 $f(t) \implies \hf_s$．

考虑快速变换的实质．
第一轮我们让所有下标 $\text{bit}_0 = 0$ 的放在左边，$\text{bit}_0 = 1$ 的放在右边．
第二轮我们让每组里面 $\text{bit}_1 = 0$ 的放在左边，$\text{bit}_1 = 1$ 的放在右边．
以此类推，最终下标 $p$ 事实上会被放到 $\text{bitreverse}(p)$ 的位置．
下标变换完了之后，我们事实上正在做一件事，就是从下往上，对于每组的左右两部分，去做赋值，也就是 $(\hf_l, \hf_r) \gets (\hf_l + \w \hf_r, \hf_l - \w \hf_r)$ 对于所有左右对应的 $(l,r)$．
$$ \begin{array}{cccccccc} 0_{(000)} & 1_{(001)} & 2_{(010)} & 3_{(011)} & 4_{(100)} & 5_{(101)} & 6_{(110)} & 7_{(111)} \end{array} \\ \begin{array}{cccc|cccc} 0_{(00\r0)} & 2_{(01\r0)} & 4_{(10\r0)} & 6_{(11\r0)} & 1_{(00\g1)} & 3_{(01\g1)} & 5_{(10\g1)} & 7_{(11\g1)} \\ \end{array} \\ \begin{array}{cc|cc|cc|cc} 0_{(0\r00)} & 4_{(1\r00)} & 2_{(0\g10)} & 6_{(1\g10)} & 1_{(0\r01)} & 5_{(1\r01)} & 3_{(0\g11)} & 7_{(1\g11)} \end{array} \\ \begin{array}{c|c|c|c|c|c|c|c} 0_{(\r000)} & 4_{(\g100)} & 2_{(\r010)} & 6_{(\g110)} & 1_{(\r001)} & 5_{(\g101)} & 3_{(\r011)} & 7_{(\g111)} \end{array} $$

那有人要问了，下标变换咋求呢？

有人问，有没有 __builtin_bitreverse32 这样的东西呢？答案是：NOI 用不了．
那有人又要问了，那如何实现这个 bitreverse 呢？总不能暴力去求吧？

这里给出一种很好写的实现．我们同样运用上面的思路，一组一组的去翻转，但是是在 uint32_t 范围内．具体来说，先是对半，再是 1/4，又是 1/8，再来 1/16，最后 1/32．看代码吧．

inline uint32_t bitreverse(uint32_t x) {
    x = x >> 16 | x << 16;
    x = (x & 0xFF00FF00u) >> 8 | (x & 0x00FF00FFu) << 8;
    x = (x & 0xF0F0F0F0u) >> 4 | (x & 0x0F0F0F0Fu) << 4;
    x = (x & 0xCCCCCCCCu) >> 2 | (x & 0x33333333u) << 2;
    x = (x & 0xAAAAAAAAu) >> 1 | (x & 0x55555555u) << 1;
}

那求 $n$ 位内的翻转，就是 bitreverse(x) >> (32-n)．

注意到逆变换和正变换的唯二区别是，单位根的符号和前面的系数．自然易于合并两段代码．

给出实现．

template<class T, class Omega> inline void Cooley_Tukey_FFT(T *a, Omega omega, uint n, bool inv) {
    const int shift = 32 - __builtin_ctz(n);
    for (uint i = 0, rev; i < n; i++)
        if (i < (rev = bitreverse(i) >> shift)) std::swap(a[i], a[rev]);
    for (uint o = 2, k, i, j; o <= n; o <<= 1) {
        const T g = inv ? omega(o) : T(1) / omega(o); T w, x, y;
        for (k = 0; k < n; k += o)
            for (i = k, j = k+o/2, w = 1; j < k+o; w *= g, i++, j++)
                x=a[i], y=w*a[j], a[i]=x+y, a[j]=x-y;
    }
    if (inv) {
        const T invn = T(1) / T(n);
        for (uint i = 0; i < n; i++) a[i] *= invn;
    }
}
template<class T> struct ComplexOmega {
    T operator()(uint n) const {
        return {cos(2*M_PI / n), sin(2*M_PI / n)};
    }
};

快速数论变换

如果现在的 $f(x)$ 是数论函数，且值域是 $\bmod m$ 意义下的，如何进行快速变换呢？

我们当然可以完全忽略这个条件，然后去做普通的 FFT，然后再取模。这样做一点问题没有，中间的值最大是 $m^2N$ 级别的，使用 long double 应该可以接受。但是程序常数就会起飞。

考虑用一个整数来替代单位根 $\w_N$．

我们目前的单位根有以下性质：

$\w_N^N=1$
$\w_{2N}^{2x} = \w_N^x$
$\w_N^{x+N} = \w_N^x$

那么考虑这样的一个单位根：$g^\frac{\varphi(m)}{N}$（有前提：$N|\varphi(m)$）
这样的单位根有一个很好的性质，就是 $g^{\varphi(m)} \equiv 1$
我们进行逐一验证：

$(g^{\frac{\varphi(m)}{N}})^N \equiv 1$ 没问题。
$(g^{\frac{\varphi(m)}{2N}})^{2x} \equiv (g^{\frac{\varphi(m)}{N}})^x$ 没问题。
$(g^{\frac{\varphi(m)}{N}})^{x+N} \equiv (g^\frac{\varphi(m)}{N})^x$ 没问题。

综上，我们就用 $g^\frac{\varphi(m)}{N}$ 替代了原来的单位根 $\w_N$．

模数单位根的计算代码

template<int g> struct ModOmega {
    Mint operator()(uint n) const {
        return Mint(g) ^ ((Mint::mod() - 1) / n);
    }
};