首先你要学会 FFT。

最初

首先考虑最 naive 的想法。

把多项式 $A(x)$ 分成 $A_0(x)+kA_1(x)$。对两个进行分拆之后我们得到

$$\begin{aligned} A(x)B(x)&=(A_0(x)+kA_1(x))(B_0(x)+kB_1(x))\\ &=A_0(x)B_0(x)+k(A_1(x)B_0(x)+A_0(x)B_1(x))+k^2A_1(x)B_1(x) \end{aligned} $$

难不成我们要做 $12$ 次 FFT？

不用不用，我们可以将相同的合并。

第一轮合并

我们只要将 $A_0(x),A_1(x),B_0(x),B_1(x)$ 做 FFT，然后对应位相乘，我们可以得到所有需要的项。

总计 $7$ 次 FFT。

第二轮合并

我们发现，在上述过程中，复数 $a+b\mathrm{i}$ 中我们只用了 $a$，并没有使用 $b$。我们尝试使用。

我们设

$$\begin{aligned} P_0(x)&=A_0(x)+\mathrm{i}A_1(x)\\ P_1(x)&=A_0(x)-\mathrm{i}A_1(x)\\ Q(x)&=B_0(x)+\mathrm{i}B_1(x) \end{aligned} $$

然后我们将他们乘起来，得到

$$\begin{aligned} P_0(x)Q(x)&=(A_0(x)+\mathrm{i}A_1(x))(B_0(x)+\mathrm{i}B_1(x))\\ &=A_0(x)B_0(x)-A_1(x)B_1(x)+\mathrm{i}(A_0(x)B_1(x)+A_1(x)B_0(x))\\ P_1(x)Q(x)&=(A_0(x)-\mathrm{i}A_1(x))(B_0(x)+\mathrm{i}B_1(x))\\ &=A_0(x)B_0(x)+A_1(x)B_1(x)+\mathrm{i}(A_0(x)B_1(x)-A_1(x)B_0(x))\\ \end{aligned} $$

于是

$$\begin{aligned} P_0(x)Q(x)+P_1(x)Q(x)&=2(A_0(x)B_0(x)+\mathrm{i}A_0(x)B_1(x))\\ P_1(x)Q(x)-P_0(x)Q(x)&=2(A_1(x)B_1(x)-\mathrm{i}A_1(x)B_0(x)) \end{aligned} $$

我们可以在上述式子中找出所有我们所需要的项。

总计 $5$ 次 FFT。

第三轮合并

本质上就是对 $P_0(x)$ 和 $P_1(x)$ 的合并。

设 FFT 长度为 $n$。根据 FFT 的定义 $\mathcal{F}(F(x))\lbrack i\rbrack=F(\omega_{n}^i)=\sum_{j=0}^{n-1}\omega_{n}^{ij}F\lbrack j\rbrack$，我们能得到

$$\begin{aligned} \mathcal{F}(P_0(x))\lbrack i\rbrack&=P_0(\omega_{n}^i)\\ &=A_0(\omega_{n}^i)+\mathrm{i}A_1(\omega_{n}^i)\\ &=\sum_{j=0}^{n-1}\omega_{n}^{ij}A_0\lbrack j\rbrack +\mathrm{i} \sum_{j=0}^{n-1}\omega_{n}^{ij}A_1\lbrack j\rbrack\\ &=\sum_{j=0}^{n-1}\omega_{n}^{ij}(A_0\lbrack j\rbrack +\mathrm{i} A_1\lbrack j\rbrack)\\ \mathcal{F}(P_1(x))\lbrack n-i\rbrack&=P_1(\omega_{n}^{-i})\\ &=A_0(\omega_{n}^{-i})-\mathrm{i}A_1(\omega_{n}^{-i})\\ &=\sum_{j=0}^{n-1}\omega_{n}^{-ij}A_0\lbrack j\rbrack -\mathrm{i} \sum_{j=0}^{n-1}\omega_{n}^{-ij}A_1\lbrack j\rbrack\\ &=\sum_{j=0}^{n-1}\omega_{n}^{-ij}(A_0\lbrack j\rbrack-\mathrm{i}A_1\lbrack j\rbrack)\\ \end{aligned} $$

考虑单位根的几何意义 $\omega_{n}^i=\cos\dfrac{2\pi i}{n}+\mathrm{i}\sin\dfrac{2\pi i}{n}$。

代入上式，得到

$$\begin{aligned} \mathcal{F}(P_0(x))\lbrack i\rbrack &=\sum_{j=0}^{n-1}\omega_{n}^{ij}(A_0\lbrack j\rbrack +\mathrm{i} A_1\lbrack j\rbrack)\\ &=\sum_{j=0}^{n-1}(\cos\dfrac{2\pi ij}{n}+\mathrm{i}\sin\dfrac{2\pi ij}{n})(A_0\lbrack j\rbrack +\mathrm{i} A_1\lbrack j\rbrack)\\ &=\sum_{j=0}^{n-1}(\cos\dfrac{2\pi ij}{n}\times A_0\lbrack j\rbrack-\sin\dfrac{2\pi ij}{n}\times A_1\lbrack j\rbrack+\mathrm{i}(\sin\dfrac{2\pi ij}{n}\times A_0\lbrack j\rbrack+\cos\dfrac{2\pi ij}{n}\times A_1\lbrack j\rbrack))\\ \mathcal{F}(P_1(x))\lbrack n-i\rbrack&=\sum_{j=0}^{n-1}\omega_{n}^{-ij}(A_0\lbrack j\rbrack-\mathrm{i}A_1\lbrack j\rbrack)\\ &=\sum_{j=0}^{n-1}(\cos\dfrac{-2\pi ij}{n}+\mathrm{i}\sin\dfrac{-2\pi ij}{n})(A_0\lbrack j\rbrack-\mathrm{i}A_1\lbrack j\rbrack)\\ &=\sum_{j=0}^{n-1}(\cos\dfrac{2\pi ij}{n}-\mathrm{i}\sin\dfrac{2\pi ij}{n})(A_0\lbrack j\rbrack-\mathrm{i}A_1\lbrack j\rbrack)\\ &=\sum_{j=0}^{n-1}(\cos\dfrac{2\pi ij}{n}\times A_0\lbrack j\rbrack-\sin\dfrac{2\pi ij}{n}\times A_1\lbrack j\rbrack-\mathrm{i}(\sin\dfrac{2\pi ij}{n}\times A_0\lbrack j\rbrack+\cos\dfrac{2\pi ij}{n}\times A_1\lbrack j\rbrack)\\ \end{aligned} $$

然后我们发现 $\mathcal{F}(P_0(x))\lbrack i\rbrack$ 和 $\mathcal{F}(P_1(x))\lbrack n-i\rbrack$ 是共轭的。（这个我在 这篇文章 里提到过）

于是我们对 $P_0$ 做 FFT 之后，可以根据定义得到 $P_1$ FFT 后的结果。

总计 $4$ 次 FFT。

听说还有另外一种合并方式？反正我不会。

第四次合并

这次合并其实没有太大效果，因为只优化掉了半次 FFT，并且还更加容易掉精度。感兴趣的读者可以自行看毛啸 2016 年集训队论文。

总计 $3.5$ 次 FFT。

针对 SP33046 这种 long double 都爆掉精度的题

要么使用任意模数 NTT（使用多个模数分别做一遍，然后使用中国剩余定理合并），要么像我这么做：

首先，对 $A_0(x),A_1(x)$ 做乘法，其他类似。

然后合并。这时候甚至只需要 double 就可以完成任务，所以效率并不是慢了 $3$ 倍。当然，在你古上不是这样的，因为你古上 long double 是 128 位的