FMT/FWT学习笔记

FMT是快速莫比乌斯变换，FWT是快速沃尔什变换。

他们两个是用来解决位运算卷积问题的。

详细点来说，已知两个多项式和一种运算。

需要快速求。

当为按位与，按位或的时候可以使用 FMT 来解决。

当为按位异或，按位同或的时候可以使用 FWT 来解决。

当为加法时就是上面讲过的 FFT/NTT。

先摆出板题：

P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

这道题里面只有与运算，或运算和异或运算，我们一个一个看。

我们令一个多项式的最高次项的项数为。

下面的所有描述都假设为的整数次幂，即恰好有的整数次幂项。

一个多项式，我们使用表示它的前半部分(次数较小的那一半)，表示它的后半部分(次数较大的后一半)，表示次方项的系数。

两个多项式，我们使用表示和逐项相加的结果；用表示和首位相接得到的结果，例如。

对于两个自然数，我们用表示，同时也可以知道。

与运算

首先我们定义一个关于多项式的函数：

简单来说，就是所有“包含” 的位置的和，也就是超集和。

我们的目标就是算出，然后算出，然后算出。

显然我们就可以在的时间内求出。

正变换

显然，这样的时间复杂度我们不太可以接受。

所以就会有一个递归公式：

正变换递归公式证明

采用数学归纳法。

当时，显然。

假设，则对于，此公式正确。

类比分治的思想，我们将一个区间分成两段，则只需要计算“跨越”中点的贡献，两边进行分治即可。

现在我们想要计算的就是向的贡献。(显然对没有贡献)

对于一个下标，现在他所缺少的贡献为。

仔细看这个，看到了什么？所以这个公式显然是正确的。

至此，我们可以在内的时间内求出。

相乘

首先有一个结论：，这里为按位乘。下来我们来证明。所以说，我们就可直接将乘起来，得到。

逆变换

现在我们知道了的值，想要求出。

我们定义的逆变换，使得。

我们可以从的定义出发，我们知道就是超集和，所以我们只需从大到小，枚举每一个数字的超集即可。

和暴力的时间复杂度是一样的，为。

显然，~~万恶的出题人表示无法接受~~。

所以还是有一个递归公式：

逆变换递归公式证明

首先我们根据数学归纳法证明与。

时显然，否则根据定义展开即可。

再进行数学归纳法证明：

当时，显然。

根据定义展开：所以

或运算

其实这里和与运算差不多，会的小伙伴可以忽略。

我们还是定义一个关于多项式的函数：

简单来说，就是所有 “包含“的位置的和，也就是子集和。

我们的目标就是算出，然后算出，然后算出。

显然我们就可以在的时间内求出。

正变换

显然，这样的时间复杂度我们不太可以接受。

所以就会有一个递归公式：

正变换递归公式证明

采用数学归纳法。

当时，显然。

假设，则对于，此公式正确。

类比分治的思想，我们将一个区间分成两段，则只需要计算“跨越”中点的贡献，两边进行分治即可。

现在我们想要计算的就是向的贡献。(显然对没有贡献)

对于一个下标，现在他所缺少的贡献为。

仔细看这个，看到了什么？

所以这个公式显然是正确的。

至此，我们可以在内的时间内求出。

相乘

首先有一个结论：，这里为按位乘。下来我们来证明。所以说，我们就可直接将乘起来，得到。

逆变换

现在我们知道了的值，想要求出。

我们定义的逆变换，使得。

我们可以从的定义出发，我们知道就是子集和，所以我们只需从大到小，枚举每一个数字的子集即可。

和暴力的时间复杂度是一样的，为。

显然，~~万恶的出题人表示无法接受~~。

所以还是有一个递归公式：

逆变换递归公式证明

首先我们根据数学归纳法证明与。

时显然，否则根据定义展开即可。

再进行数学归纳法证明：

当时，显然。

根据定义展开：所以

异或运算

这里就不是 FMT 了，就是 FWT 了。

我们还是定义一个关于多项式的函数：小朋友，你是否有很多问号。

我们的目标还是算出，然后算出，然后算出。

显然我们就可以在的时间内求出。

正变换

这个复杂度我都看不下去了。

所以又会有一个递归公式：

正变换递归公式证明

采用数学归纳法。

当时，显然。

假设，则对于，此公式正确。

类比分治的思想，我们将一个区间分成两段，则只需要计算“跨越”中点的贡献，两边进行分治即可。

先来考虑向的贡献。

对于两个数字，向贡献的系数显然和向贡献的系数相同。

即。

所以实际上对的贡献就是。

同样，向的贡献就是。

只是这个时候要注意，因为和拼在了一起，所以所有下标最高位都多了，所以要乘上，也就是公式中的那个减号。

即。

相乘

还是有一个结论：，这里为按位乘。下来我们来证明。中途用到一个小结论，就是如果那么和奇偶性相同。

考虑所有和上都是的位，因为的这一位上是，所以和肯定有且只有一个这一位上是。

如果某一位上是，上是，那么和肯定要么全是，要么全是，奇偶性不变。

如果某一位上是，那么这三个的值肯定全是。

综上所述，和无论怎么取，这两个式子的奇偶性都一样。

所以说，我们就可直接将乘起来，得到。

逆变换

现在我们知道了的值，想要求出。

定义递归公式：

现在我们想要证明

逆变换递归公式证明

首先我们根据数学归纳法证明与。

时显然，否则根据定义展开即可。

再进行数学归纳法证明：

当时，显然。

根据定义展开：所以

代码放上：

提交记录

代码

例题

例题1