FWT快速沃尔什变换
回忆一下多项式的卷积
我们可以用FFT
来做。
甚至在一些特殊情况下,我们$Ck = \sum{ij=k} A_i B_j$也能做(SDOI2015 序列统计)。
但是,如果我们把操作符换一下呢?
比如这样?
似乎这就不能用FFT
来做了。
这样子就有了FWT
——用来解决多项式的位运算卷积
最后更新于
这有帮助吗?
回忆一下多项式的卷积
我们可以用FFT
来做。
甚至在一些特殊情况下,我们$Ck = \sum{ij=k} A_i B_j$也能做(SDOI2015 序列统计)。
但是,如果我们把操作符换一下呢?
比如这样?
似乎这就不能用FFT
来做了。
这样子就有了FWT
——用来解决多项式的位运算卷积
最后更新于
这有帮助吗?