规定 \(\otimes\) 为任一位运算，给定数组 \(a_n,b_n\) ，求数组 \(\displaystyle c_n=\sum_{i\otimes j=n}a_ib_j\)
我们假设将数组 \(a_n,b_n,c_n\) 分别看成一个向量，并对该三个向量进行线性变换。
\(c_n\) 的线性变换可逆
设线性变换分别为 \(T_A,T_B,T_C\) ，且线性变换后，新数组 \(a‘_n,b‘_n,c‘_n\) 满足 \(c‘_n=a‘_n\cdot b‘_n\)
则 \(\displaystyle \sum_i T_{C(n,i)}c_i=c‘_n=a‘_n\cdot b‘_n=\sum_p T_{A(n,p)}a_p\sum_q T_{B(n,q)}b_q\)
代入 \(\displaystyle c_n=\sum_{i\otimes j=n}a_ib_j\) 得
\(\displaystyle \sum_i T_{C(n,i)}\sum_{p\otimes q}a_pb_q=\sum_p \sum_q T_{B(n,q)} T_{A(n,p)}a_pb_q\)
\(\displaystyle \sum_p\sum_q T_{C(n,p\otimes q)}a_pb_q=\sum_p \sum_q T_{B(n,q)} T_{A(n,p)}a_pb_q\)
约除相同项，我们得到 \(\displaystyle T_{C(n,p\otimes q)}=T_{B(n,q)} T_{A(n,p)}\)
由于位运算的可按位拆解性，我们得到，对于每一位 \(b\) ，都有 \(\displaystyle T_C(n_b,p_b\otimes_b q_b)=T_B(n_b,q_b) T_A(n_b,p_b)\)
又由于二进制每位的取值只有 \(0\) 或 \(1\) ，我们对于 \(T_i\) 只需要构造矩阵 \( \left( \begin{matrix} T_i(0, 0)&T_i(0, 1) \ T_i(1, 0)&T_i(1, 1) \end{matrix} \right) \) ，并且满足上述条件即可
当然 \(T_C\) 必须可逆，即 \(T_C\) 满秩，行列式 \(T_C(0, 0)T_C(1, 1)-T_C(0, 1)T_C(1, 0)\neq 0\)
当 \(\otimes\) 为按位或时：构造矩阵 \(T_A=T_B=T_C= \left( \begin{matrix} 1&1 \ 1&0 \end{matrix} \right) \)
原文：https://www.cnblogs.com/JustinRochester/p/14589653.html