首先感谢几篇良心博客的博主，教程写得真的很好。
真正理解快速沃尔什变换/快速莫比乌斯变换(FWT|FMT) (已完结)
FMT 与 子集(逆)卷积

集合卷积

我们时常要解决一些与集合有关的卷积问题，像快速傅里叶变换那样，对下标有一些要求和限制。
FWT和FMT可以成为我们解决这类问题的有力武器。

FMT

我个人认为，FMT比FWT从原理角度上更好理解。接下来介绍一下快速莫比乌斯变换。

原理

首先我们要证明FMT可以像FFT那样乘来乘去并保证正确性。

证明

对于长度为的序列，我们定义集合并卷积，

                                                                                                                        

定义它的莫比乌斯变换为

对集合并卷积的式子两边做FMT，

至此我们就证明了其具有线性变换的性质。

正变换

直接暴力进行计算，其复杂度是O()的，这个复杂度很容易证明（虽然写烂了的话就变成O()）。
一种优美的方法是分层进行递归处理，我们处理某一位i，假设一个集合S是不包含i的，那么的位置可以由S来产生贡献。
处理边界和n轮之后的变换式，就可以得到我们要的东西了。

逆变换

与正变换类似，不同点在于这次要减去SS的贡献。

这个式子用容斥证明非常容易。

Code

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

复杂度O(n2n)O(n2n)。

其他相关

有限制的FMT

现在要求

和之前不同的地方在于多了一个二者交集为空的条件，所以我们不能无脑套用FMT了。
我们可以多加一维考虑当前集合大小为ii，集合为SS的变换值。
你问为啥多加这一维？集合SS已知还要再加一位确定大小？
其实这个ii并非真实大小，而是我们认为的大小。最后有作用的只有那些f[count(S)][S]。

for (int i = 0; i <= n; ++ i)  {  for (int j = 0; i + j <= n; ++ j)  for (int S = 0; S < (1 << n); ++ S)  h[i + j][S] += f[i][S] * g[j][S]; } 

复杂度O()。

子集逆卷积

对于要求反卷积，形如

已知h,g，求f。有

现在我们要求，即一个多项式一以下的逆。然后进行FMT就万事大吉了。

inline void Inv(int *f)  {  tmp[0] = Pow(f[0], mod - 2);  for (int i = 0; i <= n; ++ i)   {  inv[i] = tmp[i];  for (int j = 0; i + j <= n; ++ j)  tmp[i + j] -= inv[i] * f[j];  } }