卷积
通用定义：
\[\text{令 } F = G\times H \text{ 。} \\ \text{则有 } f_i=\sum\limits_{x=0}^{n-1}\sum\limits_{y=0}^{n-1}g_x h_y [x\oplus y=i] \]若 \(\oplus\) 为 \(+\)，就是多项式乘法，可以使用 FFT 等手段解决。
当 \(\oplus\) 为 位运算 时，则属于位运算卷积，可用 FWT/FMT 解决。
FWT/FMT
FWT/FMT 即为 快速沃尔什变换/快速莫比乌斯变换。
这俩玩意儿网上的分类十分不清楚，所以这里也不做区分（以后也许会 upd）。
对于不同的位运算，我们有不同的做法：
Or
即 \(f[i]=\sum\limits_{x=0}^{n-1}\sum\limits_{y=0}^{n-1}g_x h_y [x\lor y=i]\)。
这里做法类似与 FFT，我们先将其转换为 \(\operatorname{FWT}[F]=\operatorname{FWT}[G] \operatorname{FWT}[H]\)，然后再通过逆变换 IFWT 弄回去。
这里我们可以定义 Or 的 FWT 形式为：\(\operatorname{FWT}[F]=\sum\limits_{i=i\lor j}f_j\)，即 \(\operatorname{FWT}[F]_i\) 的值为 \(i\) 的子集的位置对应的和。
暴力显然没有优化的空间，我们考虑分治。
方便起见，同样假设 \(n=2^k\)。
由于是或运算，所以像 FFT 那样奇偶分组不是很合理。
我们考虑反其道而行之，按最高位分组。
那么就分为 \(f_0,\cdots,f_n\) 和 \(f_{n},\cdots,f_{2n-1}\) 两部分。
分治计算时最高位不被考虑，所以前者相当于钦定了变换后最高位 \(\lor\) 为 \(0\)，后者则是钦定了最高位 \(\lor\) 为 \(1\)。
前者的答案显然正确，后者的答案则缺少一部分：最高位 \(\lor\) 为 \(0\) 的子集。
怎么补上？很简单，\(f_{n+x}+=f_x\) 即可。
逆变换呢？可以发现这就是个高维前缀和，所以做差分即可。
Code：
template<bool type,typename _Tp>
void FWT_Or(_Tp *f,int n){
for(int p=1,l=2;p<n;p=l,l<<=1)
for(int i=0;i<n;i+=l)
for(int k=0;k<p;++k) f[i|p|k]=f[i|p|k]+(type?f[i|k]:-f[i|k]/*诺，差分*/);
}
注意我们上面的一切都基于：\(\operatorname{FWT}[F]=\sum\limits_{i=i\lor j}f_j\) 转换后的乘法仍然成立。
但我们并不知道这玩意儿为什么成立……
cmd 大佬的文章用矩阵把这玩意儿手搓了出来，但是我太蒻完全看不懂。
于是有这么一个证明：
假定这个结论对 \(\operatorname{FWT}[F_0],\operatorname{FWT}[F_1]\) 分别成立，也就是我们分出的两组（最底层只有一个元素时是显然的）。
我们现在要考虑对 \(\operatorname{FWT}[F]\) 是否成立。
\[\begin{alignat}{} \operatorname{FWT}[F]&=\operatorname{FWT}[F_0],\operatorname{FWT}[F_1]+\operatorname{FWT}[F_0] \\ &=\operatorname{FWT}[G_0]\operatorname{FWT}[H_0],\operatorname{FWT}[G_0]\operatorname{FWT}[H_0]+\operatorname{FWT}[G_1]\operatorname{FWT}[H_1]+\operatorname{FWT}[G_1]\operatorname{FWT}[H_0]+\operatorname{FWT}[H_1]\operatorname{FWT}[G_0] \\ &=\operatorname{FWT}[G_0]\operatorname{FWT}[H_0],(\operatorname{FWT}[G_0]+\operatorname{FWT}[G_1])(\operatorname{FWT}[H_0]+\operatorname{FWT}[H_1]) \\ &=(\operatorname{FWT}[G_0],\operatorname{FWT}[G_0]+\operatorname{FWT}[G_1]) (\operatorname{FWT}[H_0],\operatorname{FWT}[H_0]+\operatorname{FWT}[H_1]) \\ &=\operatorname{FWT}[G] \operatorname{FWT}[H] \\ \end{alignat} \]归纳法乱搞一下就出来了。
但是第四个式子不是很知道怎么化出来的，挖坑。
然后要进行位运算卷积就类似 FFT 了，先 FWT 化出来点乘再 IFWT 化回去。
值得指出的是这里的 \(\operatorname{FWT}\) 其实是算的子集和，所以可以拿去优化一些子集问题。
And
有了 Or 打底，And 其实非常容易：
我们重新定义一下：\(\operatorname{FWT}[F]=\sum\limits_{i=i\land j}f_j\)。
然后类似地套用：
\[\operatorname{FWT}[F]= \begin{cases} F & n=1 \\ F_0+F_1,F_0 & n>1 \\ \end{cases} \]证明之类的同上，这玩意儿就是个高维后缀和。
Xor
还不会，咕。
标签：limits,sum,FFT,lor,FWT,operatorname,小记 From： https://www.cnblogs.com/LQ636721/p/17699505.html