快速莫比乌斯变换笔记

本地笔记整理，原文写于 2019/7/31，2019/12/8 上传

这个枚举子集啊从 \(\mathcal O(4^n)\) 到 \(\mathcal O(3^n)\) 只优化了一半，最后的目标一定是 \(\mathcal O(2^n)\)！ ——MR

考虑加速在序列 \(\{a\}, \{b\}\) 上的集合并卷积： \[ c_k = \sum_{i \cup j = k} a_ib_j \] 利用和 FFT 类似的思想，考虑构造变换 \(\operatorname{FMT}\{a\}\)，使得： \[ \operatorname{FMT}\{a\}_i\times\operatorname{FMT}\{b\}_i = \operatorname{FMT}\{c\}_i \] 观察到可以构造： \[ \operatorname{FMT}\{a\}_i = \sum_{j \subseteq i} a_j \] 即前缀子集和。该变换成立的原因显然。

然而朴素构造子集和的时间复杂度是 \(O(3^n)\) 的，有没有办法优化呢？

显然是有的，我们采用增量的方法，逐个考虑集合的每个元素 \(x\)，如果一个集合 \(i\) 应该包含 \(x\)，则其子集可以包含也可以不包含 \(x\)，因此进行操作：\(a_i = a_i + a_{i\setminus x}\)

代码是很短的：

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]

时间复杂度为 \[ \sum_{i = 0}^{n - 1} 2^{n - i - 1}\cdot 2^i = O(n2^n) \]