「postOI」以另一种方式证明 FWT

记号

\(\otimes\) 代表或/与/异或卷积；
\(\oplus\) 代表“拼接”，例如 \(A\oplus B\) 即将 \(B\) 接在 \(A\) 的后面；
\(+,-,\times\) 代表按位运算，例如 \(A+B=\{a_0+b_0,a_1+b_1,...,a_n + b_n\}\)；
\(F(A)\) 代表 \(A\) 进行 fwt 后的序列；
\(A_0\) 代表 \(A\) 的前半部分，\(A_1\) 代表 \(A\) 的后半部分，\(A_0\oplus A_1 = A\)

或卷积

直接给出或FWT的递归形式：

\[F(A)=\begin{cases}F(A_0) \oplus F(A_0+A_1)&|A| > 1\\A&|A|=1\end{cases}
\]

接下来是一些性质：

\(F(A + B) = F(A) + F(B)\)，这一点比较明显；
\(F(A\otimes B)=F(A) \times F(B)\)，直接证明比较麻烦，我们考虑归纳证明。

易知在 \(|A| = |B| = 1\) 时，上述结论成立。

假设已经证明了对于 \(|A| = |B| = \frac n2\) 上述结论成立，下证对于 \(|A| = |B| = n\) 成立。

首先一个简单的分析——考虑 \(A_0\) 和 \(A_1\)，其实下标上只有最高位上 \(A_0\) 是 \(0\)，\(A_1\) 是 \(1\) 的区别。然后我们再考虑 \((A \otimes B)_0\)，既然是或卷积，最高位是 \(0\)，那肯定参与的下标都是最高位为 \(0\)，也即

\[(A \otimes B)_0 = A_0 \times B_0
\]

稍微复杂的是 \((A \otimes B)_1\)，要求最高位至少有一个 \(1\)，也就是说

\[(A \otimes B)_1 = A_0 \otimes B_1 + A_1 \otimes B_0 + A_1 \otimes B_1
\]

有了以上的结论就可以完成或卷积性质的证明了：

\[\begin{aligned}
F(A \otimes B) &= F\Big[(A \otimes B)_0\Big] \oplus F\Big[(A \otimes B)_0 + (A \otimes B)_1\Big]\\
&= F(A_0\otimes B_0) \oplus F(A_0 \otimes B_0 + A_0 \otimes B_1 + A_1 \otimes B_0 + A_1 \otimes B_1)\\
&= [F(A_0) \times F(B_0)] \oplus [F(A_0 + A_1) \times F(B_0 + B_1)]\\
&= [F(A_0) \oplus F(A_0 + A_1)] \times [F(B_0) \oplus F(B_0 + B_1)] & \text{(按位运算)}\\
&= F(A) \times F(B)
\end{aligned}
\]

与卷积与或卷积相同。

异或卷积

同样的，我们可以得到

\[\begin{matrix}
(A \otimes B)_0 = A_0 \otimes B_0 + A_1 \otimes B_1\\
(A \otimes B)_1 = A_0 \otimes B_1 + A_1 \otimes B_0
\end{matrix}
\]

然后给出异或FWT的递归式：

\[F(A)=\begin{cases}
F(A_0 + A_1) \oplus F(A_0 - A_1)&|A| > 1\\
A&|A| = 1
\end{cases}
\]

接下来是类似的归纳推导：

\[\begin{aligned}
F(A \otimes B) &= F[(A \otimes B)_0 + (A \otimes B)_1] \oplus F[(A \otimes B)_0 - (A \otimes B)_1]\\
&= F(A_0 \otimes B_0 + A_1 \otimes B_1 + A_0 \otimes B_1 + A_1 \otimes B_0) \oplus F(A_0 \otimes B_0 + A_1 \otimes B_1 - A_0 \otimes B_1 - A_1 \otimes B_0)\\
&= [F(A_0 + A_1) \times F(B_0 + B_1)] \oplus [F(A_0 - A_1) \times F(B_0 - B_1)]\\
&= [F(A_0 + A_1) \oplus F(A_0 - A_1)] \times [F(B_0 + B_1) \otimes F(B_0 - B_1)]\\
&= F(A) \times F(B)
\end{aligned}
\]

小记

之前推导 FWT 是正向的构造，虽然构造非常巧妙，但是不太好理解。尤其是异或卷积利用到“异或后二进制位 1 的个数的奇偶性不变”这种虽然明显，但并不好用的性质。

现在能找到一种用归纳法证明 FWT 的方式，感觉非常直接，所以记下来了。

巴特西

「postOI」以另一种方式证明 FWT

记号

或卷积

异或卷积

小记

最新文章

热门文章