快速沃尔什变换

快速沃尔什变换,简称 FWT ,目前在 OI 中十分冷门。

用处

多项式卷积一般是这样的:

$$ C_i = \sum_{j + k = i} A_j \cdot B_k $$

这个可以用 FFT 快速求解。

然而还有一个诡异的卷积:

$$ C_i = \sum_{j \oplus k = i} A_j \cdot B_k $$

其中 $ \oplus $ 是任意一种位运算。

FWT 便是求这类卷积的快速算法。

构造

FFT 的思想是把多项式转换成可以线性相乘的点值表示法 (DFT) ,
再把相乘的结果转换回系数表示法 (IDFT) 。

同样的道理可以用在 FWT 上,用 DWT 将多项式转换成可以线性相乘的形式,即:

$$ DWT(C)_i = DWT(A)_i \cdot DWT(B)_i $$

再用 IDWT 将相乘的结果转换回来。

DWT

目标是构造一个转移系数函数 f(i, j) ,满足:

$$ DWT(A)_i = \sum_j A_j \cdot f(i, j) $$

考虑 f(i, j) 应满足什么样的性质。

首先根据 DWT 的性质:

$$ DWT(C)_i = DWT(A)_i \cdot DWT(B)_i $$

$$ \sum_t C_t f(i, t) = \sum_j A_j f(i, j) \sum_k B_k f(i, k) $$

$$ \sum_t \sum_{j \oplus k = t} A_j B_k f(i, t) = \sum_j \sum_k A_j f(i, j) B_k f(i, k) $$

$$ \sum_t \sum_{j \oplus k = t} A_j B_k f(i, t) = \sum_t \sum_{j \oplus k = t} A_j f(i, j) B_k f(i, k) $$

由上式可得出:

$$ \forall i, j, k: f(i, j) f(i, k) = f(i, j \oplus k) $$

这样还不够,为了让 DWT 快速进行,f(i, j) 还应满足以下性质:

$$ f(i, j) = \prod_k f(i_k, j_k) $$

其中 $ i_k $ 表示 i 二进制下的第 k 位( 0 或 1 )。

有了这个性质,就可已通过 f(0, 0), f(0, 1), f(1, 0), f(1, 1) 的值相乘得出所有 f 。
有了这个性质,就可以考虑分治求 DWT :

$$ DWT(A)_i = \sum_{j=0}^{n-1} A_j f(i, j) $$

$$ = \sum_{j=0}^{n/2-1} A_j f(i, j) + \sum_{j=n/2}^{n-1} A_j f(i, j) $$

$$ = \sum_{j=0}^{n/2-1} A_j \prod_k f(i_k, j_k) + \sum_{j=n/2}^{n-1} A_j \prod_k f(i_k, j_k) $$

$$ = \sum_{j=0}^{n/2-1} f(i_0, j_0) A_j \prod_{k \geq 1} f(i_k, j_k) + \sum_{j=n/2}^{n-1} A_j f(i_0, j_0) \prod_{k \geq 1} f(i_k, j_k)$$

$$ = f(i_0, 0) \sum_{j=0}^{n/2-1} A_j \prod_k f(i_k, j_k) + f(i_0, 1) \sum_{j=n/2}^{n-1} A_j \prod_k f(i_k, j_k) $$

规模减小了一半,递归或迭代地分治下去。
每次将 A 分成左右两半 A0, A1 :

$$ DWT(A)_i = f(0, 0) DWT(A0)_i + f(0, 1) DWT(A1)_i , i < n / 2 $$

$$ DWT(A)_i = f(1, 0) DWT(A0)_i + f(1, 1) DWT(A1)_i , i \geq n / 2 $$

想到 FFT 的蝴蝶变换没有? 答:没有
迭代的 DWT 这里也有类似的蝴蝶变换:

int x = A[i], y = A[i + k];
A[i] = f00 * x + f01 * y;
A[i + k] = f10 * x + f11 * y;

DWT 的过程就是这样了,甚至不需要构造整个 f ,
只需要 f(0, 0), f(0, 1), f(1, 0), f(1, 1) 即可,
需要满足的就是 $ \forall i, j, k: f(i, j) f(i, k) = f(i, j \oplus k) $ 。

IDWT

怎么将 DWT 的结果转换回来?
观察 DWT 的蝴蝶变换:

a = f00 * x + f01 * y;
b = f10 * x + f11 * y;

DWT 通过 x, y 求出 a, b,
IDWT 就是通过 a, b 求 x, y 。

解二元一次方程就好了:
x = (f11 * a – f01 * b) / (f00 * f11 – f01 * f10)
y = (f10 * a – f00 * b) / (f01 * f10 – f00 * f11)

就是这么简单…

个屁啊。

考虑 f 的构造,
要满足 DWT 的性质把所有的 f 设为 0 不就可以了?
要满足 DWT 的性质把所有的 f 设为 1 不就可以了?

这样且不是对于任何位运算都会有相同的结果?

Naive.

再看看 IDWT ,分母里边是不是有 (f01 * f11 – f01 * f10) ?
不幸的是把 f 全部设为 0 或者全设为 1 这个分母都是 0 ,
这意味着 IDWT 的二元一次方程无解,转过去就转不回来了。

因此 f 的构造还要满足一个条件: f01 * f11 != f01 * f10

f 的构造

f 需要满足的性质已经讲的很详细了。

这里给出常用位运算中 f 的构造:

  • 按位或: f00 = 1, f01 = 0, f10 = 1, f11 = 1
  • 按位与: f00 = 1, f01 = 1, f10 = 0, f11 = 1
  • 异或: f00 = 1, f01 = 1, f10 = 1, f01 = -1

可以自行验证,这些 f 满足上述性质。

实际意义

一个多项式 A FFT 后的 A2(x) 实际意义就是 A 在 $ W_n^x $ 上的值(点值表示)。

那么 A FWT 后的结果的现实意义呢?
这得分类来说。

按位或

A 在做按位或的 FWT 之后得到的 A2 满足:
$$ A2(x) = \sum_{i|x=x} A(i) $$

也就是说 A2(x) 表示 x 的每个子集 i 的 A(i) 的和。
不难得到,A2(x) * B2(x) 的结果 C2(x) 就是 A, B 卷积后的 C 的变换:
$$ A2(x) * B2(x) = \sum_{i|x=x} A(i) \sum_{j|x=x} B(j) $$
$$ A2(x) * B2(x) = \sum_{i|x=x} \sum_{j|x=x} A(i) B(j) $$
$$ A2(x) * B2(x) = \sum_{k|x=x} \sum_{i|j=k} A(i) B(j) $$
$$ A2(x) * B2(x) = \sum_{k|x=x} C(k) $$
$$ A2(x) * B2(x) = C2(x) $$

事实上,这也就是子集和变换。

感性理解一下

按位与

和按位或类似的,A 在做按位与的 FWT 之后得到的 A2 满足:
$$ A2(x) = \sum_{i\&x=x} A(i) $$

也就是说 A2(x) 表示每个包含 x 的集合 i 的 A(i) 的和。
不难得到,A2(x) * B2(x) 的结果 C2(x) 就是 A, B 卷积后的 C 的变换:
$$ A2(x) * B2(x) = \sum_{i\&x=x} A(i) \sum_{j\&x=x} B(j) $$
$$ A2(x) * B2(x) = \sum_{i\&x=x} \sum_{j\&x=x} A(i) B(j) $$
$$ A2(x) * B2(x) = \sum_{k\&x=x} \sum_{i\&j=k} A(i) B(j) $$
$$ A2(x) * B2(x) = \sum_{k\&x=x} C(k) $$
$$ A2(x) * B2(x) = C2(x) $$

和按位或一个模子里刻出来的

子集卷积

两个多项式 A, B 的子集卷积 C 的意义如下:

$$ C(x) = \sum_{y|z=x, y\&z=0} A(y) B(z) $$

也就是把 x 划分为两个子集 y, z 的 A(y) * B(z) 的和。

转换成 $ \sum_{y|z=x} A(y) B(z) [y \& z = 0] $ ,似乎是一个按位或卷积。
再转换成 $ \sum_{y|z=x} A(y) B(z) [bitcount(y) + bitcount(z) = bitcount(x)] $ 。

此时需要考虑的就是 bitcount, 也就是集合大小。
集合大小是 $ O(log(n)) $ 的,可以考虑枚举大小,设:
$$ A_i(x) = A(x) [bitcount(x) = i] $$
$$ B_j(x) = B(x) [bitcount(x) = j] $$
$$ C_k(x) = C(x) [bitcount(x) = k] $$

那么有:
$$ C_k(x) = \sum_{y|z=x} A_i(y) B_j(z) [i + j = k] $$
$$ C_k(x) = \sum_{i+j=k} \sum_{y|z=x} A_i(y) B_j(z) $$

那么枚举 i, j 的值,将 $ A_i $ 和 $ B_j $ 卷积后贡献到 $ C_{i+j} $ 即可。

这样复杂度似乎是 $ O(n log^3n) $ 的,
但是事实上每个 $ A_i, B_j $ 都可以提前 FWT 后 $ O(n) $ 相乘,
再贡献到 C 后不进行逆变换,而是确定了 C 的值后在进行逆变换。

复杂度 $ O(n log^2n) $

分类: 二进制

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: