写在前面

由于本蒟蒻理解也不透彻，这篇博客只讲怎么做，没有证明 没有证明 没有证明。

先说是拿来干嘛的

FMT是用来求解下面这种形式的“卷积”的：

\[h(U) = \sum_{S \cup T = U} f(S) \cdot g(T)
\]

叫做“集合并卷积”

其中\(U\)，\(S\)，\(T\)是集合，用二进制数表示集合就是：

\[h(k) = \sum_{i | j = k} f(i) \cdot g(j)
\]

具体做法

类似\(FFT\)这种，\(FMT\)也是先将\(f\)和\(g\)变换成点值表达，点值对应数乘后再变换回去就可以求得\(h\)，也就是\(FMT(h) = FMT(f) \cdot FMT(g)\)，中间的点是数乘

于是有一种方案就是莫比乌斯变换，即\(\hat{f}(S) = \sum_{T \subseteq S} f(T)\)

它的逆变换就是\(f(S) = \sum_{T \subseteq S} (-1)^{|S| - |T|} \hat{f} (T)\)，证明可以容斥，具体……看这篇博客最上面……

那么就可以\(O(3^n)\)暴力枚举子集来（逆）变换了

但是还有更快的方法

\(O(n \cdot 2^n)\)的快速变换

令：

\[\hat{f}_S^{(i)} = \sum_{T \subseteq S} [(S - T) \subseteq \{ 1, 2, ..., i \}]f_T
\]

易得：

\[\hat{f}_S^{(0)} = f_S \\
\hat{f}_S^{(n)} = \sum_{T \subseteq S}[(S - T) \subseteq \{ 1, 2, ..., n\}]f_T = \sum_{T \subseteq S}f_T = \hat{f} (S)
\]

且对于不包含\(i\)的\(S\)，有递推式：

\[\hat{f}_S^{(i)} = \hat{f}_S^{(i - 1)} \tag{1}
\]

\[\hat{f}_{S \cup \{ i \}}^{(i)} = \hat{f}_S^{(i - 1)} + \hat{f}_{S \cup \{ i \}}^{(i - 1)} \tag{2}
\]

简单理解一下就是：

\((1)\)式：因为\(S\)不包含\(i\)，所以满足条件的子集不会变

\((2)\)式：前一部分为\(S - T\)不包含\(i\)的情况，后一部分为\(S - T\)一定包含\(i\)的情况

这样经过\(n\)轮递推，就可以求得\(\hat{f}_S^{(i)}\)，也就是\(\hat{f} (S)\)了，复杂度\(O(n \cdot 2^n)\)

代码

void FMT(double *a, int n) {
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < (1 << n); ++j)
			if (j & (1 << i)) a[j] += a[j ^ (1 << i)];
}

逆变换把+=换成-=就好了，不过如果是浮点运算，要注意精度问题

void IFMT(double *a, int n) {
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < (1 << n); ++j)
			if (j & (1 << i)) a[j] -= a[j ^ (1 << i)];
}

例题

如果需要，移步[HAOI2015]按位或

挖坑：集合卷积

大概很快就会填坑吧……