多项式乘法

假定你拥有高中数学基础。

复数

复数的三角形式可以表示为 $a=r(\cos\theta + i\sin \theta)$。
那么假定 $a=r_1(\cos\alpha + i\sin \alpha),b=r_2(\cos\beta + i\sin\beta)$，有 $ab=r_1 r_2(\cos\alpha\cos\beta-\sin\alpha\sin\beta + i\cos\alpha\sin\beta + i\cos\beta\sin\alpha)=r_1r_2(\cos(\alpha + \beta)+i\sin(\alpha+\beta))$，也就是说，模长相乘，辐角相加，即棣莫弗定理。

由复数的三角形式，我们画一个单位圆，以 $(1,0)$ 为起点，在圆上等间距画出 $n$ 个点，这样得到的 $n$ 个复数便是 $n$ 次单位根，转到的第一个记作 $\omega_n$，有 $\omega_n^n =1$。

欧拉公式：$e^{ix}=\cos x + i\sin x$。

快速傅里叶变换

设 $F(x)=\sum\limits_{i=0}^{n-1} a_i\times x^i$，那么这是多项式的系数表示法。

由拉格朗日插值可知，我们搞 $n$ 个不重复的点也可以确定一个 $n-1$ 次多项式，这是多项式的点值表示法。

FFT

我们现在假定（$n$ 为偶数）：

$$F_1(x)=a_0+a_2\times x + a_4\times x^2+\cdots a_{n-2}\times x^{n/2-1}\\ F_2(x)=a_1+a_3\times x + a_5\times x^2 +\cdots a_{n-1}\times x^{n/2-1}$$

那么 $F(x)=F_1(x^2)+x F_2(x^2)$。并且：

$$\begin{aligned} F(\omega_n^{k})&=F_1(\omega_n^{2k})+\omega_{n}^k F_2(\omega_n^{2k})\\ &=F_1(\omega_{n/2}^{k})+\omega_{n}^k F_2(\omega_{n/2}^{k}) \end{aligned} \\ \begin{aligned} F(\omega_n^{k+n/2})&=F_1(\omega_n^{2k})+\omega_{n}^{k+n/2} F_2(\omega_n^{2k})\\ &=F_1(\omega_n^{2k})-\omega_{n}^{k} F_2(\omega_n^{2k}) \end{aligned}$$

通过这样的方式，我们可以以 $O(n\log n)$ 的时间复杂度在已知一个多项式的系数表示时求得它的点值表示，在求出两个多项式的点值表示后，我们就可以计算 $H(x)=F(x)G(x)$，进而得到两多项式乘积的点值表示。

IFFT

我们现在要将点值表示转化为系数表示，我们现在得到了 $n$ 个点 $(\omega_{n}^i,y_i=F(\omega_{n}^i))$。

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void FFT(int L, Complex *f, int type) { // L 表示长度, type = 1 表示 FFT, type = 0 表示 IFFT
    static int r[N];
    for (int i = 1; i < L; ++i) {
        r[i] = (r[i >> 1] >> 1) + (i & 1 ? L >> 1 : 0);
        if (i < r[i]) swap(f[i], f[r[i]]);
    }
    for (int d = 1; d < L; d <<= 1) {
        Complex wd(cos(PI / d), sin(PI / d)); // 2d 次单位根
        wd.b *= type; // IFFT 单位根取倒数, 相当于沿 x 轴对称
        static Complex w[N];
        w[0] = Complex(1, 0);
        for (int j = 1; j < d; ++j) w[j] = w[j - 1] * wd; // 用数组记录 0 ~ d-1 次单位根, 减少复数乘法次数
        for (int i = 0; i < L; i += d << 1)
            for (int j = 0; j < d; ++j) {
                Complex x = f[i | j], y = w[j] * f[i | j | d];
                f[i | j] = x + y, f[i | j | d] = x - y;
            }
    }
    if (type == -1) for (int i = 0; i < L; ++i) f[i] = f[i] / L;
}

三次变两次优化

我们考虑 $(f+gi)^2=f^2-g^2+2fgi$，因此有 三次变两次。