集合幂级数
从 \(2^U\rightarrow R\) 的映射
加法乘法
\(h=f\cdot g=\sum\limits_{L\in 2^U}\sum\limits_{R\in 2^U}f_Lg_Rx^{L\oplus R}\)
类比乘法，其中 \(\oplus\) 需要满足交换律，结合律
高维前缀和的 dp 解释
设 \(f_{S,i}\) 表示考虑 \(S\) 的子集的后 \(i\) 位，前 \(|S|-i\) 位与 \(S\) 相同
或卷积
核心：对最高位进行分治，结合位运算的独立性，可以按任意顺序处理每一位
\(p,q\) 的对应位分别为 \(0,1\)，FMT 操作 \(q+p\)，FMI 操作 \(q-p\)，二者互为逆变换
理解为高维前缀和
与卷积
FMT 操作 \(p+q\)，FMI 操作 \(p-q\)
理解为高维后缀和
异或卷积
直接构造出 FWT 的变换形式：\(\hat{f_S}=\sum\limits_{T\in 2^U}(-1)^{|S\cap T|}f_T\)
FWT 逆变换：\(f_S=\dfrac{1}{2^n}\sum\limits_{T\in 2^U}(-1)^{|S\cap T|}\hat{f_T}\)
还是进行分治，FWT 操作 \(p\leftarrow p+q,q\leftarrow p-q\)，FWI 操作 \(p\leftarrow \dfrac{p+q}{2},q\leftarrow \dfrac{p-q}{2}\)，相当于将 \(2^n\) 分摊到 \(n\) 层中
性质
FMT 和 FWT 可以理解为矩阵乘法，也就是线性变换，具有线性性。
若干 \(f\) 卷可以先都转化为点值，对应相乘，再转回来，类似于 fft
子集卷积
带上 \(\text{popcount}\)，先都转为点值，再对应相乘，再转回来