FWT学习笔记

FWT

$C_k=\sum_{i\oplus j=k}A_iB_j$

记为$C=A*B$

$FWT[C]=FWT[A]\cdot FWT[B]$ ($\cdot$表示点积)

设$FWT[A][i]=\sum_{j=0}^{n-1} c(i,j)A[j]$

根据定义有
$$
\begin{aligned}
&\because\forall i\in[0,n)\cap\Z,FWT[C]i=FWT[A]i\times FWT[B]i\\
&\begin{aligned}\therefore\sum{j=0}^{n-1}c(i,j)C_j&=\left(\sum{j=0}^{n-1}c(i,j)A_j\right)\times\left(\sum{j=0}^{n-1}c(i,j)B_j\right)\\
&=\sum_{j=0}^{n-1}\left(c(i,j)A_j\sum_{k=0}^{n-1}c(i,k)B_k\right)\\
&=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k
\end{aligned}\\
&又C_j=\sum_{j=i_1\oplus i_2}A_{i_1}B_{i_2}\\
&\begin{aligned}即\sum_{j=0}^{n-1}c(i,j)C_j&=\sum_{j=0}^{n-1}c(i,j)\sum_{j=i_1\oplus i_2}A_{i_1}B_{i_2}\\
&=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j\oplus k)A_{j}B_{k}\\
&=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k
\end{aligned}\\
\end{aligned}
$$
所求即为$c(i,j)c(i,k)=c(i,j\oplus k)$