集合并卷积与FMT

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

集合卷积

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

FMT

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

原理

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

证明

对于长度为 ${2}^{n}$ 的序列，我们定义集合并卷积，

$h_{S} = \sum_{L \subseteq S} \sum_{R \subseteq S} [L \cup R = S]f_{L} * g_{R}.$

定义它的莫比乌斯变换为

$\widehat{h_{S} } = \sum_{L \subseteq S} h_{L}.$

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

$\widehat{h_{S} } = \sum_{T \subseteq S} \sum_{L \subseteq T} \sum_{R \subseteq T} [L \cup R = T] f_{L} * g_{R}.$

$\widehat{h_{S} } = \sum_{L \subseteq S} \sum_{R \subseteq S} [L \cup R \subseteq S] f_{L} * g_{R}.$

$\widehat{h_{S} } = \widehat{f_{S} } * \widehat{g_{S} }.$

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

正变换

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

逆变换

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

$h_{S} = \sum_{T \subseteq S} {(-1)}^{|S|-|T|} \widehat{h_{T} }.$

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

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

现在要求

$h_{S} = \sum_{L \subseteq S} \sum_{R \subseteq S} [L \cup R = S, L \cap R = \phi] f_{L} * g_{R}.$

和之前不同的地方在于多了一个二者交集为空的条件，所以我们不能无脑套用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( $n^22^n$ )。

子集逆卷积

对于要求反卷积，形如

$h=f*g{}$

已知h,g，求f。有

$f = h * {g}^{-1}.$

现在我们要求 $g_{-1}$ ，即一个多项式一以下的逆。然后进行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];  } }