FWT

处理问题$$C_i = \sum\limits_{i \oplus j} A_iB_j$$ 离散沃尔什变换「DWT」设 $DWT_i (A) = \sum\limits_{j = 0}^n A_jf(i, j)$ （第一次知道原来离散变换是这么设的） 又由于$$\begin{aligned}DWT_i(A)DWT_i(B) &= DWT_i(C) \\\sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j)f(i, k) &= \sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j \oplus k)\end{aligned}$$故 $f(i, j)f(i, k) = f(i, j \oplus k)​$ 于是就有一些结论 $and: f(i, j) = [(i and j) = i]$ $or: f(i, j) = [(i and j) = j]$ $xor: f(i, j) = (- ...