文章链接:http://orzsiyuan.com/archives/Algorithm/Fast-Walsh-Hadamard-Transform 快速沃尔什变换用于解决多项式位运算卷积。其计算过程和 类似。 概述 首先我们回忆一下多项式卷积: 在[「算法笔记」快速傅里叶变换 FFT](http://orzsiyuan.com/archives/Algorithm/Fast-Fourier-Transform) 中我们将多项式 和 转化为点值表达,然后重新转化为系数表达。 接下来考虑如下卷积形式: 其中 分别表示按位或、按位与、按位异或。 这样就没法使用 解决了,我们需要引进...