Appearance
二进制卷积
快速傅里叶变换可以高效地计算两个多项式的乘积,进而加速了卷积运算。
序列
构造多项式
我们知道
现在考虑一类奇怪的卷积:
其中
面对这类奇葩的卷积时,FFT 就束手无策了。
0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 0 |
还有高手?
快速沃尔什变换(Fast Walsh-Hadamard Transform,FWT)是加速 二进制卷积 运算的算法,其大方向与 FFT 非常相似。
回忆一下 FFT 如何加速多项式乘法:
- 对
和 使用 DFT,得到两个点集: - 计算出
的点值表示法: - 使用 IDFT 将其转化为系数表示法。
我们在 DFT 和 IDFT 中使用 FFT 的思想来加速这个过程。
FWT 也是同样的套路:
- 对序列
使用 FWT,得到两个中间态(中间态也是序列): - 使用点对点乘法,计算出
的中间态: - 使用
UFWT
(也称IFWT
)将其还原为序列。
只不过 FWT 的中间态略显抽象,并且
OR 卷积
在
🤔
沃尔什究竟是怎么想出来的?
设有两个序列
可以证明,对
容易发现
可以从集合意义理解:若
接下来的证明步骤会用到该结论。
证毕。
现在推导一下中间态的求法。
类似于 FFT,此处也规定所有序列的长度
我们将序列
然后仔细盯真
- 当
时,由 运算的性质可知, 中 的大小不可能超过 。因此 也落在 的范围内,也就是说 只能来自 ,即 ,即 - 当
时, 既可以来自 ,又可以来自 。由于 是一个求和式,我们可以顺理成章地把它拆成两个部分的和 注:此处对 减去 是为了调整下标,使其适应相应的分段序列。或者说, 和 的长度都只有 ,作此调整可以防止数组访问越界。
即
更进一步地,以序列为基本单位看问题:
其中
上面我们已经剖析了 FWT 的算法,现在还需要讨论其反演 UFWT
。
其实只要把点对点加法 UFWT
的递推式。
容易证明
此论断等价于
设序列
由于
现假设命题对
由式
因此
因此
即命题对
模板
cpp
void FWT_OR(vector<int>& a, int l, int r, bool inv) {
if (l == r)
return;
int mid = (l + r) >> 1;
FWT_OR(a, l, mid, inv);
FWT_OR(a, mid + 1, r, inv);
for (int i = 0; i <= mid - l; i ++) {
if (!inv)
a[mid + 1 + i] += a[l + i];
else
a[mid + 1 + i] -= a[l + i];
}
}
AND 卷积
类似可证
由于
模板
cpp
void FWT_AND(vector<int>& a, int l, int r, bool inv) {
if (l == r)
return;
int mid = (l + r) >> 1;
FWT_AND(a, l, mid, inv);
FWT_AND(a, mid + 1, r, inv);
for (int i = 0; i <= mid - l; i ++) {
if (!inv)
a[l + i] += a[mid + 1 + i];
else
a[l + i] -= a[mid + 1 + i];
}
}
XOR 卷积
设序列
其中
要使
将
在
即得
注意到
其中
TIP
这个结论是显然的。在二进制按位异或的过程中:
- 若
当前位均为 ,则 的该位为 ,相当于少了两个 , 的奇偶性没变; - 若一个是
,另一个是 ,则 的该位为 ,相当于没差; - 若都是
也没差。
既然奇偶性相同,那么
又注意到
代入
于是便可以确定函数
该形式完美符合
从而序列
现对
- 当
时,直接把求和式拆分成两半: - 当
时,需要对下标 进行偏移,偏移量为 ,理由同 OR 卷积。 需要注意的是,当 取 时, ,下标偏移导致了此处符号的改变。
即
进一步地
对应地
其中对序列的除法运算也是点对点除法。
模板
cpp
void FWT_XOR(vector<int>& a, int l, int r, bool inv) {
if (l == r)
return;
int mid = (l + r) >> 1;
FWT_XOR(a, l, mid, inv);
FWT_XOR(a, mid + 1, r, inv);
for (int i = 0; i <= mid - l; i ++) {
int u = a[l + i], v = a[mid + 1 + i];
a[l + i] = u + v;
a[mid + 1 + i] = u - v;
}
if (inv) {
for (int i = l; i <= r; i ++) {
a[i] /= 2;
}
}
}