思路
FWT 用以快速求：
\[h(x)\sum_{a\oplus b=x}f(a)g(b)
\]
其中 \(\oplus\) 可以是很多操作，常见的比如按位与、或、异或等。
我们考虑构造一种映射 \(\mathrm{FWT}\)，满足：
\[\mathrm{FWT}(h)=\mathrm{FWT}(f)\cdot\mathrm{FWT}(g)
\]
和 FFT 很像。
常见实现
按位或
一种可行的构造为：
\[\mathrm{FWT}(f)(i)=\sum_{j|i=i}f(j)
\]
考虑如何快速变换。存在分治做法：
每次将当前序列分为左右两部分，则左侧当前最高位为 \(0\)，右侧当前最高位为 \(1\)，先递归处理两部分，然后将左侧的答案加到右侧对应位置即可。当前最高位是关于下标的，可以感性理解，理性理解的话就是一侧的块长关于 \(2\) 的对数那一位。
记分出来的两半序列为 \(f_0,f_1\)，\(\mathrm{merge}\) 表示拼接两个序列，那么可以写作：
\[\mathrm{FWT}(f)=\mathrm{merge}(f_0,f_1+f_0)
\]
逆变换的话减掉就行了：
\[\mathrm{IFWT}(f)=\mathrm{merge}(f_0,f_1-f_0)
\]
通常使用非递归实现。
按位与
和按位或很像，一种可行的构造为：
\[\mathrm{FWT}(f)(i)=\sum_{j\&i=i}f(j)
\]
剩下的也基本一样，也是分治：
\[\mathrm{FWT}(f)=\mathrm{merge}(f_0+f_1,f_1)
\]
逆变换：
\[\mathrm{IFWT}(f)=\mathrm{merge}(f_0-f_1,f_1)
\]
按位异或
记 \(x\circ y=\mathrm{popcnt}(x\&y)\bmod 2\)，那么有 \((x\circ y)\oplus(x\circ z)=x\circ(y\oplus z)\)。
存在构造：
\[\mathrm{FWT}(f)(i)=\sum_{j\circ i=0}f(j)-\sum_{j\circ i=1}f(j)
\]
存在分治做法：
\[\mathrm{FWT}(f)=\mathrm{merge}(f_0+f_1,f_0-f_1)
\]
逆变换：
\[\mathrm{IFWT}(f)=\mathrm{merge}(\frac{f_0+f_1}{2},\frac{f_0-f_1}{2})
\]
三份代码
注意逆运算时 orFWT 和 andFWT \(x\) 带入 \(-1\)，xorFWT 带入 \(\frac{1}{2}\)。
inline vec<mint> orFWT(vec<mint> v,mint x=1){int n=v.size();for(int st=2,k=1;st<=n;st<<=1,k<<=1)for(int i=0;i<n;i+=st)repl(j,0,k)v[i+j+k]+=v[i+j]*x;return v;
}
inline vec<mint> andFWT(vec<mint> v,mint x=1){int n=v.size();for(int st=2,k=1;st<=n;st<<=1,k<<=1)for(int i=0;i<n;i+=st)repl(j,0,k)v[i+j]+=v[i+j+k]*x;return v;
}
inline vec<mint> xorFWT(vec<mint> v,mint x=1){int n=v.size();for(int st=2,k=1;st<=n;st<<=1,k<<=1)for(int i=0;i<n;i+=st)repl(j,0,k)v[i+j]+=v[i+j+k],v[i+j+k]=v[i+j]-v[i+j+k]-v[i+j+k],v[i+j]*=x,v[i+j+k]*=x;return v;
}