快速沃尔什变换 | KeBlog

[Kewth]

https://kewth.github.io/2019/11/03/%E5%BF%AB%E9%80%9F%E6%B2%83%E5%B0%94%E4%BB%80%E5%8F%98%E6%8D%A2/

快速沃尔什变换，简称 FWT ，目前在 OI 中十分冷门。用处多项式卷积一般是这样的：$$ Ci = \sum{j + k = i} A_j \cdot B_k $$这个可以用 FFT 快速求解。然而还有一个诡异的卷积：$$ Ci = \sum{j \oplus k = i} A_j \cdot B_k $$

[SakuNight]

感觉不是很冷门的样子QAQ

[Kewth]

@ChiTongZ 感觉不是很冷门的样子QAQ

emm 好像我写的时候比较无知，以为这东西没什么用，现在看来好像确实不冷门。。。