位运算卷积
快速求序列 \(C\)：
\[C_i=\sum_{j\oplus k=i}A_jB_k \]其中 \(\oplus=or,and,xor\)。
类似 FFT 的思路，对于序列 \(a\) 构造新序列 \(fmt(a)\)，使得满足 \(fmt(a*b)_i=fmt(a)_i\times fmt(b)_i\)
在位运算情况下，\(fmt(a)_i\) 均可以表达成关于序列 \(a\) 的可逆线性变换，即：
\[fmt(a)_i=\sum_j g(i, j)a_j \]将这个表达式带入上面 \(fmt\) 的性质：
\[\begin{aligned} fmt(a*b)_i &= fmt(a)_i\times fmt(b)_i \\ \sum_x g(i, x)(a*b)_x &= \sum_yg(i,y)a_y\sum_zg(i,z)b_z \\ \sum_j\sum_kg(i, j\oplus k)a_jb_k &= \sum_y\sum_zg(i, x)g(i, y)a_yb_z \end{aligned} \]考虑直接令 \(j=y,k=z\) 的每一对 \((j,k,y,z)\) 都存在 \(g(i,j\oplus k)=g(i,x)g(i,y)\) 即可满足性质。
分别将 \(\oplus\) 带入 \(or,and,xor\) 找到合适的函数 \(g\)。
or
\(g(i, x)=[x\subset i]\)。
即对 \(i\) 求 子集和。
\(fwt\quad ifwt\)：SOSDP。
and
\(g(i, x)=[x\supset i]\)。
即对 \(i\) 求 超集和。
\(fwt\quad ifwt\)：SOSDP。
xor
\(g(i,x)= (-1)^{|x\cap i|}\)
\(fwt\) 操作：\(A={A_0+A_1},A_0-A_1\)
\(ifwt\) 操作：\(A=\frac{1}{2}(A_0+A_1),\frac{1}{2}(A_0-A_1)\)
可以手动验证上述函数的正确性。
标签：xor,运算,卷积,fmt,ifwt,fwt,oplus,sum From： https://www.cnblogs.com/edisnimorF/p/18032864