FMT快速莫比乌斯变换

2020-01-12 本文已影响0人 Tacmon_old

请大家注意：

因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。

问题模型

快速求 $f(S) = \sum_{A \cup B = S} g(A)h(B)$ 。

公式推导

原式等价与：
$f(S) = \sum_{A \subseteq S} \sum_{B \subseteq S} [A \cup B =S]g(A)h(B)$
$f(S) = \sum_{A \subseteq S} g(A) \sum_{B \subseteq S} h(B)[A \cup B = S]$
那么我们设：
$\begin{align} \hat f(S) &= \sum_{T \subseteq S} f(T) \\ \hat g(S) &= \sum_{T \subseteq S} g(T) \\ \hat h(S) &= \sum_{T \subseteq S} h(T) \end{align}$
就有：
$\hat f(S) = \hat g(S) \times \hat h(S)$
之后可以用之前的子集反演得到：
$f(S) = \sum_{T \subseteq S} (-1)^{|S-T|} \hat f(T)$
现在问题就是如何快速的在 $\hat f$ 与 $f$ 之间变换。
由于 $3^n$ 的枚举子集过于简单，就不讲了，在这里介绍 $O(n2^n)$ 的做法：
我们先考虑正变换，考虑递推：
设 $\hat f_{i}(S)$ 表示 $\sum_{T \subseteq S} [(S-T) \subseteq \{0,1,2,...,i\}] f(T)$
那么我们有： $\hat f_{0}(S) = f(S)$
然后对于所有不包含 $i+1$ 这个元素的集合 $S$ ，有：
$\hat f_{i+1}(S) = \hat f_{i}(S)$
$\hat f_{i+1}(S \cup \{i+1\}) = \hat f_{i}(S \cup \{i+1\}) + \hat f_{i}(S)$
那么 $\hat f_n$ 即为所求。
接下来我们考虑反演，求出答案：
我们类似的定义 $f_{i}(S)$ ，那么对于所有不包含 $i$ 这个元素的集合 $S$ ，有：
$f_{i-1}(S) = f_{i}(S)$
$f_{i-1}(S \cup \{i\}) = f_{i}(S \cup \{i\}) - f_{i}(S)$
最后 $f_0$ 即为所求。
又因为每一位（每一个元素）是独立的，所以我们可以从 $0 \sim n$ 而不是从 $n \sim 0$ 。
那么我们就做完了。