用处
处理一些位运算卷积，\(O(n2^n)\)
\[c_i=\sum_{k \oplus j=i} a_k\times b_j
\]
大体思想
构造某种映射，使得能够 \(O(n\log n)\) 内得到变换，假设原数列为 \({a_n}\)，新数列就是 \({fwt[a]_i}\)。
然后知道了 \({fwt[a]_i}\) 和 \({fwt[b]_i}\)，能 \(O(n)\) 得到 \({fwt[c]_i}\)
最后还能够 \(O(n\log n)\) 将 \(fwt[c]_i\) 变换为 \(c_i\)
其实和 FFT 很像，就是解析式到点值再到解析式。
构造方法
Or
构造 \(fwt[a]_i=\sum_{j|i=i} a_j\)，也就是对 \(i\) 的所有子集求和。
这个构造有性质如下：
\[\begin{align}
fwt[a]_i\times fwt[b]_i&=\sum_{j|i=i} \sum_{k|i=i} a_j\times b_k \&=\sum_{(j|k)|i=i} a_j\times b_k \&=fwt[c]_i
\end{align}
\]
假设现在处理完了前 \(w-1\) 位的 \(fwt[c]_i\)，考虑怎么加入第 \(w\) 位的贡献。如果一个数的第 \(w\) 位是 0 ，那么它的或卷积是不会变的，如果是 1，那么答案就要累加上最高位为 1 的卷积。然后逆变换也是类似的，只是符号反过来。
\[fwt[a]_i=merge(fwt[a_0]_i,fwt[a_0]_i+fwt[a_1]_i)
\]
\(merge\) 表拼接。
void Or(int n,ll *a,bool op){
for(int w=2,l=1;w<=n;w<<=1,l<<=1)
for(int j=0;j<n;j+=w)
for(int k=0;k<l;k++)
a[j|k|l]=(a[j|k|l]+(op? -1:1)*a[j|k]+Mod)%Mod;
}
And
与卷积与或卷积类似，有
\[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i)
\]
void And(int n,ll *a,bool op){
for(int w=2,l=1;w<=n;w<<=1,l<<=1)
for(int j=0;j<n;j+=w)
for(int k=0;k<l;k++)
a[j|k]=(a[j|k]+(op? -1:1)*a[j|k|l]+Mod)%Mod;
}
Xor
构造运算 \(x\otimes y=count(x\&y) \bmod 2\)
有性质
\[(x\otimes y) \ xor \ (x\otimes z)=x\otimes(y^z)
\]
可以构造变换 \(fwt[a]_i=\sum_{i\otimes j=0} a_j-\sum_{i\otimes j=1}a_j\)
得到
\[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i-fwt[a_1]_i)
\]
逆变时要除以 2。
void Xor(int n,ll *a,ll op){
ll x,y;
for(int w=2,l=1;w<=n;w<<=1,l<<=1)
for(int j=0;j<n;j+=w)
for(int k=0;k<l;k++)
x=(a[j|k]+a[j|k|l])%Mod*op%Mod,
y=(a[j|k]-a[j|k|l]+Mod)%Mod*op%Mod,
a[j|k]=x,a[j|k|l]=y;
}