更多精彩尽在这里,详情点击:https://robynschat.com/,斯特林

个点分成若干个圆排列的方案数,就相当于枚举了置换的方案数。因此上式成立。

最简单的当然就是直接根据递推式来求啦,但是有时候这样的复杂度不够优秀,因此我们需要一点更加优秀的求解方法。

根据第一类斯特林数和上升次幂/下降次幂的关系,我们可以知道将特定的一些下降/上升次幂展开后系数的第\(k\)次项的绝对值就是要求的斯特林数的第\(k\)项。

而上升/下降次幂可以看做一些多项式相乘(本身展开后就是多项式,而不同的上升/下降次幂可以通过合并不同的上升/下降次幂得到)

首先每一层的复杂度要计算\(n\)个点,一共有\(logn\)层,一共计算\(nlogn\)个元素,每个元素的复杂度是\(logn\)的,所以总复杂度\(nlog^2n\)。

如果我们可以用同一层的前半部分快速求出后半部分,那么我们每次就只需要递归前半部分,那么我们就不用在每一层都对当前层所有的元素的计算,而只需要对一小块计算。

因为对每个点进行计算的复杂度仍然是\(logn\)级别的,所以我们的总复杂度就可以做到\(nlogn\)。

考虑到后者其实是在用1个点,不断的乘2,最后得到整个序列。因此我们将它称之为倍增FFT。

本作品采用知识共享署名-非商业性使用-禁止演绎 3.0 未本地化版本许可协议进行许可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Copyright © All right reserved.