概览
将对数列的讨论带到了二进制上，用于解决跟操作二进制位的符号有关的题目
如
\[\sum_{i|j=k}a[i]·b[j] \]FFT的大概流程是将多项式化为点值表达式，然后通过点值表达式\(O(n)\)复杂度的合并降低复杂度上限，最后将点值表达式化回多项式
第一步和第三步的复杂度是\(O(n\log n)\)的，因此复杂度就被压下来了
FWT类似，因为FWT部分操作的可乘性，所以让人想到了可以先把多项式化成FWT中的形式，操作后再变回去
于是就有了FWT（Fast Walsh Transform）
大概思想如此，在或运算实现中可设
\[fa[i]=\sum_{j|i=i}a[j]\\ fb[i]=\sum_{k|i=i}b[j] \]然后能发现\(fa[i]*fb[i]\)得到的\(fc[i]\)为
\[fc[i]=\sum_{j|i=i}a[j]·\sum_{k|i=i}b[j]\\ fc[i]=\sum_{j|i=i}\sum_{k|i=i}a[j]·b[j]\\ fc[i]=\sum_{j|k=i}a[j]·b[j] \]以上式子自己试着推一遍就能理解
AND，XOR的处理类似，不过XOR的稍微复杂
例题：FWT模板，子集卷积
子集卷积是对FWT的一种活学活用
大部分都是套OR模板，但因为要保证$i\cap j=\varnothing \(即\) |i|+|j|=|k|\(，所以要多开一维记录当前\)i$的位数
标签：96th,多项式,sum,2024,fc,点值,FWT,复杂度 From： https://www.cnblogs.com/tlz-place/p/18440817