简单的整理了一下目前自己会的鬼畜东西QAQ
快速沃尔什变换
新的卷积
卷积的东西都很好玩呀。有时间一定好好学泛函.jpg
前面提到了，离散傅里叶变换的多项式卷积是对于每个 k 获得 i+j=k 的 \sum a_i \times a_j，而在数论中比较多的狄利克雷卷积是对于每个 k 获得 i \times j = k 的 \sum a_i \times a_j。在实际题目中，我们可能会遇到这样的一类卷积：
对于每个 k，获得 i \otimes j = k 的 \sum a_i \times a_j。其中 \otimes 是任意按位逻辑运算，如 \&, |, \oplus 等。