FWT

作者: ffacs 分类: 总结 发布时间: 2020-07-15 19:46

引入


$$
\sum_{i=1}^n c_i=\sum_{j\oplus k=i} a_jb_k (n\le 1e5)
$$
其中 $\oplus$ 表示一种二元位运算

与、或

正变换

对于 按位或 运算,我们若有 $i\ \text{or}\ k=k$ 和 $j\ \text{or}\ k=k$ 则有 $(i\ \text{or}\ j) \text{or}\ k=k$

如果有
$$
\begin{align}
a'_i&=\sum_{j\ \text{or}\ i=i} a_j \\
b'_i&=\sum_{k\ \text{or}\ i=i} b_k
\end{align}
$$
则有
$$
\begin{align}
c'_i&=\sum_{l\ \text{or}\ i=i}c_l\\
&=\sum_{l\ \text{or}\ i=i}\sum_{j\ \text{or}\ k=l} a_jb_k \\
&=\sum_{(j\ \text{or}\ k)\ \text{or}\ i=i} a_jb_k \\
&=\sum_{j\ \text{or}\ i=i} \sum_{k\ \text{or}\ i=i}a_j b_k \\
&=\sum_{j\ \text{or}\ i=i} a_j\sum_{k\ \text{or}\ i=i} b_k \\
&=a_i'*b_i'
\end{align}
$$
如果能对 $a,b$ 进行快速变换,我们就能得到 $c$ 快速变换的结果。之后再进行快速逆变换就得到 $c$ 了。

设 $dp$ 为最高的 $i$ 位与 $j$ 相同满足且 $k\ \text{or}\ j=j$ 的 $\sum a_k$ 则显然当$i>\left\lfloor \log_2n\right\rfloor$ 时,$dp[i,j]=a'_j$ 。

若 $j$ 的第 $i$ 高位为 $0$ 则有
$$
\begin{align}
dp\left[i,j\right]&=dp\left[i-1,j\right]\\
dp[i,j+2^i]&=dp[i-1,j]+dp[i-1,j+2^i]
\end{align}
$$

那么同理,对于 与运算,我们也能得到转移方程
$$
\begin{aligned}
dp[i,j]&=dp[i-1,j]+dp[i-1,j+2^i]\\
dp[i,j+2^i]&=dp[i-1,j+2^i]
\end{aligned}
$$

逆变换

我们现在已经知道 $c’_i$ 了,要想求 $c_i$ 只需要将正变换的转移方程反过来,逆向推即可。

所以有

或:
$$
\begin{aligned}
dp[i,j]&=dp[i+1,j],\\
dp[i,j+2^i]&=dp[i+1,j+2^i]-dp[i+1,j]
\end{aligned}
$$

与:
$$
\begin{aligned}
dp[i,j]&=dp[i+1,j]-dp[i+1,j+2^i],\\
dp[i,j+2^i]&=dp[i+1,j+2^i]
\end{aligned}
$$

$c_i=dp[1,i]$

异或

正变换

若我们 令二元运算 $x\otimes y=\text{popcount}(x\ \text{and}\ y)\bmod 2$ ,则有 $(i\otimes j)\ \text{xor}\ (i\otimes k)=i\otimes(j\ \text{xor}\ k)$

如果有
$$
a’i=\sum_{i\otimes j=0}a_j-\sum_{i\otimes j=1}a_j\\
b’i=\sum_{i\otimes k=0}b_k-\sum_{i\otimes k=1}b_k\\
$$
则有
$$
\begin{align}
c'_i&=\sum_{i\otimes l=0}c_l-\sum_{i\otimes l=1}c_l\\
&=\sum_{i\otimes l=0}\sum_{j\ \text{xor}\ k=l} a_jb_k-\sum_{i\otimes l=1}\sum_{j\ \text{xor}\ k=l} a_jb_k\\
&=\sum_{i\otimes(j\ \text{xor} \ k)=0}a_jb_k-\sum_{i\otimes(j\ \text{xor} \ k)=1}a_jb_k \\
&=\sum_{(i\otimes j)\ \text{xor}\ (i\otimes k)=0}a_jb_k-\sum_{(i\otimes j)\ \text{xor}\ (i\otimes k)=1}a_jb_k \\
&=\sum_{i\otimes j=0}a_j\sum_{i \otimes k=0}b_k+\sum_{i\otimes j=1}a_j\sum_{i \otimes k=1}b_k-(\sum_{i\otimes j=0}a_j\sum_{i \otimes k=1}b_k+\sum_{i\otimes j=1}a_j\sum_{i \otimes k=0}b_k) \\
&=\sum_{i\otimes j=0}a_j(\sum_{i \otimes k=0}b_k-\sum_{i \otimes k=1}b_k)-\sum_{i\otimes j=1}a_j(\sum_{i \otimes k=0}b_k-\sum_{i \otimes k=1}b_k) \\
&=(\sum_{i\otimes j=0}a_j-\sum_{i\otimes j=1}a_j)(\sum_{i \otimes k=0}b_k-\sum_{i \otimes k=1}b_k)\\ &=a'_ib'_i
\end{align}
$$

我们就构造出了 $\text{FWT}$ 变换的规则。

仍然采用上面的状态定义。我们有:
$$
\begin{aligned}
dp[i,j]&=dp[i-1,j]+dp[i-1,j+2^i],\\
dp[i,j+2^i]&=dp[i-1,j]-dp[i-1,j+2^i]
\end{aligned}
$$

逆变换

$$
\begin{aligned}
dp[i,j]&=\frac{dp[i+1,j]+dp[i+1,j+2^i]}{2},\\
dp[i,j+2^i]&=\frac{dp[i+1,j]-dp[i+1,dp[j+2^i]]}{2}
\end{aligned}
$$

发表评论

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