FMT与FWT

Posted on | In ,

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

集合卷积

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

FMT

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

原理

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

证明

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

定义它的莫比乌斯变换为

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

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

正变换

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

逆变换

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

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

Code

1
2
3
4
5
6
7
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)];
}

复杂度。

其他相关

有限制的FMT

现在要求

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

1
2
3
4
5
6
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}^{2} {2}^{n})$。

子集逆卷积

对于要求反卷积，形如

已知$h,g$，求$f$。有

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

1
2
3
4
5
6
7
8
9
10
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];
    }
}

FWT

我们已经会了一些FMT的基本操作，可以解决部分集合并、集合交的问题。
但是除了刚才那样容斥，我们还有快速沃尔什变换。

0%