快速莫比乌斯变换笔记

Posted on 2019-07-31 Edited on 2020-08-06 Views:

本地笔记整理，原文写于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) 的，有没有办法优化呢?

显然是有的，我们采用增量的方法，逐个考虑集合的每个元素，如果一个集合应该包含，则其子集可以包含也可以不包含，因此进行操作： $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)$