算法学习笔记:FMT

引例

集合并卷积问题:

$$f(S)=\sum_{T_1\cup T_2=S}g(T_1)\cdot h(T_2)$$

请求出某个集合的所有子集的$f$值。集合大小$n\le 20$。

另外还有集合交卷积:

$$f(S)=\sum_{T_1\cap T_2=S}g(T_1)\cdot h(T_2)$$

分析

好像可以一眼看出这个问题可以使用FWT在$O(n\cdot 2^n)$的时间内解决。但是FWT好像要背几个式子。

这里介绍一种更简单的方法:快速懵逼莫比乌斯变换。

快速莫比乌斯变换(FMT)

先来解决集合并卷积:

$$f(S)=\sum_{T_1\cup T_2=S}g(T_1)\cdot h(T_2)$$

直接求不好求,定义一个辅助函数$\hat f(S)$,表示$S$所有子集的$f$值之和:

$$ \begin{align} \hat f(S)&=\sum_{T_1\cup T_2\subset S}g(T_1)\cdot h(T_2) \\ &=\sum_{T_1, T_2\subset S}g(T_1)\cdot h(T_2)\\ &=\sum_{T\subset S}g(T)\cdot \sum_{T\subset S}h(T)\\ &=\hat g(S)\cdot \hat h(S) \end{align} $$

这样只要我们能快速做$f(S)$与$\hat f(S)$之间的变换,就可以快速做卷积了,类似FFT转成点值表达式的操作。

至于变换的方法,裸的枚举子集是$O(3^n)$的。考虑dp,设$dp(i,S)$从$S$删去$1\dots i$之间的一些元素,得到的所有集合的$f$值之和,则:

$$dp(i,S)=dp(i-1,S)+dp(i-1,S-{i})$$

前者表示不删$i$,后者表示删$i$。这样dp的复杂度就是$O(n\cdot 2^n)$的。

同样我们还需要考虑$\hat f$转成$f$的变换(好像叫莫比乌斯反演)。根据容斥原理:

$$f(S)=\sum_{T\subset S}(-1)^{|S|-|T|}\cdot \hat f(T)$$

其实就是多了个$(-1 )^n$的系数。方程改为:

$$dp(i,S)=dp(i-1,S)-dp(i-1,S-\{i\})$$

后者改为减号,是因为集合大小每减少$1$,系数就会多乘一个$-1$。

这样集合并卷积就做完了,考虑集合交卷积,实际上把二进制位全部取反就是并卷积了。

代码

集合并卷积:

dp的第一维显然可以压掉。$p=1$表示正变换,$p=0$表示逆变换。

for (int i = 1; i < n; i <<= 1)
      for (int j = 0; j < n; j++)
            if (j & i) f[j] += p ? f[j^i] : -f[j^i];

集合交卷积:

与并卷积的差别只有所有二进制位反转,所以只需改if语句的条件。

for (int i = 1; i < n; i <<= 1)
      for (int j = 0; j < n; j++)
            if (!(j & i)) f[j] += p ? f[j^i] : -f[j^i];

比FWT写得舒适多了。

不过异或卷积还是只能用FWT。

子集卷积

来看这个问题:

$$f(S)=\sum_{T_1\cup T_2=S且T_1\cap T_2=\emptyset}g(T_1)\cdot h(T_2)$$

与并卷积相比多了一个条件:$T_1\cap T_2=\emptyset$,这样就不能直接卷积了。因为$T_1\cup T_2=S$,所以这个条件可以转化为$|T_1|+|T_2|=|S|$。我们设$f(i,S)$表示只考虑恰有$i$个元素的集合时$f(S)$的值,显然只有$i= S$时$f(i,S)\neq 0$。这样定义看似没有意义,但是我们可以发现$f(i)=\sum_{j=1}^{i}g(j)*h(i-j)$,这里的乘号表示卷积。

然后我们只要枚举$i$,枚举$j$,每次做一遍卷积就完事了。不过可以预处理的时候先把$g,h$数组每层都FMT好,这样卷积时只要$O(2^n)$对应位相乘就好了。总复杂度$O(n^2\cdot 2^n)$。

总结:子集卷积可能会遇到对集合大小有限制的情况,此时可以多开一维记集合大小。



转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论