“⊕”是按位异或运算。
我认为Karatsuba算法可能可以解决该问题，但是当我尝试在Karatsuba算法中使用XOR代替“+”时，很难得到子问题。
The 卷积定理 https://en.wikipedia.org/wiki/Convolution_theorem给你
F(C) = F(A) . F(B)
where F是一个与傅里叶相关的变换，在本例中是哈达玛变换，并且.是逐点乘法。使用快速沃尔什-阿达玛变换 https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform，你可以计算F(A), F(B)，最后C（使用逆），在O(n log n)运营。逐点乘法很简单O(n).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
