论文鸽在群里说了一下这个东西,我也实现了一下,发现效果还不错。
由于这个 exp 的 \(O(n\log n)\) 算法非常的慢,所以我们一般采用 \(O(n\log^2 n)\) 的分治 FFT 来求解。
普通的分治 FFT 已经可以与论文鸽的 exp 五五开了,但是有没有更快的方法呢?
注意,这个优化只能在 cdq FFT 的时候采用,也就是说不能优化 n 个一次多项式的卷积之类的问题。
我们先来回忆一下普通的分治 FFT 是如何做的。
我们假设 \(F(x) = e^{G(X)}\),这里我们知道 \(G(x)\),我们要求解 \(F(x)\)。
两侧求导,得 \(F^{'}(x) = e^{G(X)} \times G^{'}(X) = F(X) \times G^{'}(X)\)
也就是说我们是对这个式子进行求解:\(F^{'}(x) = F(X) \times G^{'}(X)\)
我们采用 \(solve(l, r)\) 表示求解 \(F(X)\) 的第 \(l\) 项到第 \(r\) 项。
取区间中点 \(mid\)。
先调用 \(solve(l, mid)\) 来求解出前半部分。
再计算左侧对右侧的贡献。
再调用 \(solve(mid + 1, r)\) 来求解出后半部分。
这就是普通的分治 FFT。
首先分治 FFT 是一个树状结构,我们往往可以尝试增加一层往下的分支数来优化深度。
我们设分支数为 \(B\)。
如果直接分治 FFT,那么需要计算每个儿子对后面儿子的贡献,每次计算需要一个长度为 \(O(n / B)\) 的卷积(\(n\)为目前分治区间长度)。
也就是说时间复杂度 \(T(n) = B \times T(\frac{n}{B}) + B \times n \times \log {\frac{n}{b}}\),大力求解得 \(B=2\) 时最优。
我是不是在玩你。
好的我们继续。
我们真的是每一对儿子都要用一次卷积来计算贡献吗?
我们可以先求出这个儿子的点值,考虑它对后面儿子的贡献,这个儿子的点值就不用重复计算了。
存储前面儿子对它的贡献的时候,你也可以直接存储点值,最后一次 FFT 转换即可,也不用多次计算了。
而卷上的是 \(G^{'}(x)\) 的一个区间,这个区间的点值也可以提前计算。
也就是说我们只需要 \(O(B)\) 次长度为 \(O(n / B)\) 的 FFT 了!
因此计算贡献的部分复杂度变为了 \(O(B^2 \times \frac{n}{B} + B \times \frac{n}{b} \times \log {\frac{n}{b}})\),
即 \(O(Bn + n \times \log {\frac{n}{b}})\)。
时间复杂度 \(T(n) = B \times T(\frac{n}{B}) + Bn + n \times \log {\frac{n}{b}}\)。不错,求解一下。
发现 \(B = O(\log n)\) 的时候最优秀,时间复杂度为\(O(\frac{n\log^2n}{\log \log n})\)。
事实上由于计算贡献的时候非常的****,可以使用 avx2 进行优化,亲测一定的常数优化之后进行 \(4 \times 10^6\) 的 exp 只需要 1.5s。
当然其他类似的 cdq FFT 也可以这样进行优化,祝大家早日吊打 \(O(n\log n)\)。
原文:https://www.cnblogs.com/skip1978/p/12408384.html