关于 FWT 的一些理解

规定 \(\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)\)

上一篇:Educational Codeforces Round 108 (Rated for Div. 2) C


下一篇:5706. 句子相似性 III