快速莫比乌斯变换笔记
本地笔记整理,原文写于2019/7/31,2019/12/8上传
这个枚举子集啊从
到
只优化了一半,最后的目标一定是
! ——MR
考虑加速在序列上的集合并卷积:
然而朴素构造子集和的时间复杂度是的,有没有办法优化呢?
显然是有的,我们采用增量的方法,逐个考虑集合的每个元素,如果一个集合
应该包含
,则其子集可以包含也可以不包含
,因此进行操作:
代码是很短的:
for (int i = 1; i < (1 << n); i <<= 1) // 枚举元素
for (int s = i << 1, l = 0; l < (1 << n); l += s) // [l, l + s) 是一段区间
for (int k = 0; k < i; k++) // 其中前半段没有i,后半段有i
a[l + i + k] += a[l + k]
逆向变换的代码也很简单:
for (int i = 1; i < (1 << n); i <<= 1)
for (int s = i << 1, l = 0; l < (1 << n); l += s)
for (int k = 0; k < i; k++)
a[l + i + k] -= a[l + k]
时间复杂度为