本文介绍了如何计算具有时间复杂度O(n log n)的XOR(二进)卷积的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在此处输入图片描述

⊕"是按位XOR运算.

"⊕" is the bitwise XOR operation.

我认为Karatsuba的算法可以用来解决问题,但是当我尝试使用XOR而不是"+"时,在唐津算法中,很难找到子问题.

I think Karatsuba’s algorithm may be used to solve the problem, but when I try to use XOR instead of "+" in the Karatsuba’s algorithm, it is tough to get the sub-problem.

推荐答案

卷积定理给你

F(C) = F(A) . F(B)

其中 F 是与傅立叶相关的变换,在本例中为Hadamard变换,而.是逐点乘法.使用快速Walsh–Hadamard变换,您可以计算F(A) F(B),最后是 C (使用反码),以 O(n log n)操作.逐点乘法就是 O(n).

where F is a Fourier-related transform, in this case the Hadamard transform, and . is point-wise multiplication. Using the fast Walsh–Hadamard transform, you can compute F(A), F(B), and finally C (using the inverse), in O(n log n) operations. The point-wise multiplication is simply O(n).

这篇关于如何计算具有时间复杂度O(n log n)的XOR(二进)卷积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-23 15:34