FWT

liujiageng · 2024-11-19 10:18:05 · 个人记录

FWT(A_i)=FWT(B_i)*FWT(C_i)

- $FWT_{or}(A_i)=\displaystyle\sum_{j为i子集}{a_j}

位矩阵 \begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} 逆矩阵 \begin{bmatrix} 1 & 0\\ -1 & 1 \end{bmatrix}

- $FWT_{and}(A_i)=\displaystyle\sum_{j为i超集}{a_j}

位矩阵 \begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix} 逆矩阵 \begin{bmatrix} 1 & -1\\ 0 & 1 \end{bmatrix}

- $FWT_{xor}(A_i)=\displaystyle\sum_j (-1)^{i\ and\ j}a_i

位矩阵 \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} 逆矩阵 \begin{bmatrix} \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & -\frac{1}{2} \end{bmatrix}

code