如何优化这个异或和算法？

Question

我正在尝试解决这个 hackerrank 问题https://www.hackerrank.com/challenges/xor-subsequence/problem

\n

from functools import reduce\n\ndef xor_sum(arr):\n    return reduce(lambda x,y: x^y, arr)    \n\ndef xorSubsequence(arr):\n    freq = {}\n    max_c = float("-inf") # init val\n    min_n = float("inf") # init val\n    \n    for slice_size in range(1, len(arr)+1):\n        for step in range(0, len(arr)+1-slice_size):\n            n = xor_sum(arr[i] for i in range(step,step+slice_size))\n            \n            freq[n] = freq.get(n,0)+1\n            if freq[n] >= max_c and (n < min_n or freq[n]> max_c):\n                min_n = n\n                max_c = freq[n]\n\n    return  min_n, freq[min_n]\n

\n

但它超时了，因为它是 ~O(n^3)。\n我觉得有一些数学技巧，有人可以向我解释解决方案吗？我尝试阅读讨论中的一些解决方案，但我不太明白。

\n

问题副本：

\n

\n

考虑一个由n 个整数组成的数组A ( A=a ₀ ,a ₁ ,...,a _n-1 )。我们从数组中获取\n满足以下条件的所有连续整数子序列：\n{ a _i ,a _i+1 ,...,a _j-1 ,a _j }，其中 0\xe2\x89\xa4 i\ xe2\x89\xa4j\xe2\x89\xa4n

\n

对于每个子序列，我们对所有整数应用按位 XOR (\xe2\x8a\x95) 运算并记录结果值。

\n

给定数组A ，求A的每个子序列的 XOR 和，并确定每个数字出现的频率。\n然后在一行上打印该数字及其各自的频率\n 两个空格分隔的值。

\n

输出格式

\n

在一行上打印 2 个以空格分隔的整数。\n第一个整数应该是出现频率最高的数字，\n第二个整数应该是该数字的频率\n（即出现的次数）。 \n如果有多个数字具有最大频率，\n选择最小的一个。

\n

约束条件

\n

\xe2\x80\xa2 1\xe2\x89\xa4n\xe2\x89\xa410 ⁵
\n\xe2\x80\xa2 1\xe2\x89\xa4a_我<2 ¹⁶

\n

\n

Answer 1

该解决方案使用了两个技巧。

\n

第一个技巧是计算 n+1 前缀和 \xcf\x83[0]、\xe2\x80\xa6、\xcf\x83[n] （如tobias_k注释），但使用 XOR 而不是 +（例如，\xcf \x83[2] = a[0] 异或 a[1] 异或 a[2])。从 i 到 j 的子列表的异或和等于 \xcf\x83[i\xe2\x88\x921] XOR \xcf\x83[j]。如果我们在所有可能的值对 0、\xe2\x80\xa6、n 上循环 i\xe2\x88\x921 和 j，而不考虑约束 i \xe2\x89\xa4 j，我们将得到每个子列表两次（一次 \xe2 \x80\x9cforward\xe2\x80\x9d，一次 \xe2\x80\x9cbackward\xe2\x80\x9d)，并且从 i\xe2\x88\x921 = j 开始还有 n+1 个额外的零。

\n

第二个技巧是快速 Walsh\xe2\x80\x93Hadamard 变换可以在 O(n log n) 时间内解决以下问题：给定列表 X 和列表 Y，我们想要 x XOR y 的频率计数 (x , y) \xe2\x88\x88 X \xc3\x97 Y。（对于这个问题，X = Y，但是如果我使用单独的变量，这个技巧的结构会更清晰。）为什么我们应该怀疑有一个快速算法首先？抛开限制不谈，如果是 x + y 而不是 x XOR y，那么我们将寻求快速乘以多项式。

\n

让\xe2\x80\x99s 用它的频率向量 f 替换列表 X，用它的频率向量 g 替换 Y。例如，X = [0, 0, 0, 2, 2, 3] 变为 f = [3, 0, 2, 1]。假设 f 和 g 有四个元素，期望的结果是

\n

[f[0] g[0] + f[1] g[1] + f[2] g[2] + f[3] g[3]\n,f[0] g[1] + f[1] g[0] + f[2] g[3] + f[3] g[2]\n,f[0] g[2] + f[1] g[3] + f[2] g[0] + f[3] g[1]\n,f[0] g[3] + f[1] g[2] + f[2] g[1] + f[3] g[0]\n].\n

\n

这是称为对称双线性形式的代数对象的示例，这意味着存在一些基变化矩阵 B，使得所需结果为 B\xe2\x81\xbb\xc2\xb9 (B f * B g)，其中 * 表示逐元素乘法。（剧透：B 是沃尔什矩阵。）

\n

对于快速 Walsh\xe2\x80\x93Hadamard 变换（对于每个向量 v 都可以有效地计算 B v）的直觉，让我向您展示当我添加结果的前两个元素时会发生什么：

\n

f[0] g[0] + f[1] g[1] + f[2] g[2] + f[3] g[3]\n+ f[0] g[1] + f[1] g[0] + f[2] g[3] + f[3] g[2]\n= f[0] (g[0] + g[1]) + f[1] (g[1] + g[0]) + f[2] (g[2] + g[3]) + f[3] (g[3] + g[2])\n= (f[0] + f[1]) (g[0] + g[1]) + (f[2] + f[3]) (g[2] + g[3])\n

\n

并添加后两个元素：

\n

f[0] g[2] + f[1] g[3] + f[2] g[0] + f[3] g[1]\n+ f[0] g[3] + f[1] g[2] + f[2] g[1] + f[3] g[0]\n= f[0] (g[2] + g[3]) + f[1] (g[3] + g[2]) + f[2] (g[0] + g[1]) + f[3] (g[1] + g[0])\n= (f[0] + f[1]) (g[2] + g[3]) + (f[2] + f[3]) (g[0] + g[1])\n

\n

并减去前两个元素：

\n

f[0] g[0] + f[1] g[1] + f[2] g[2] + f[3] g[3]\n\xe2\x88\x92 (f[0] g[1] + f[1] g[0] + f[2] g[3] + f[3] g[2])\n= f[0] (g[0] \xe2\x88\x92 g[1]) + f[1] (g[1] \xe2\x88\x92 g[0]) + f[2] (g[2] \xe2\x88\x92 g[3]) + f[3] (g[3] \xe2\x88\x92 g[2])\n= (f[0] \xe2\x88\x92 f[1]) (g[0] \xe2\x88\x92 g[1]) + (f[2] \xe2\x88\x92 f[3]) (g[2] \xe2\x88\x92 g[3])\n

\n

并减去后两个元素：

\n

f[0] g[2] + f[1] g[3] + f[2] g[0] + f[3] g[1]\n\xe2\x88\x92 (f[0] g[3] + f[1] g[2] + f[2] g[1] + f[3] g[0])\n= f[0] (g[2] \xe2\x88\x92 g[3]) + f[1] (g[3] \xe2\x88\x92 g[2]) + f[2] (g[0] \xe2\x88\x92 g[1]) + f[3] (g[1] \xe2\x88\x92 g[0])\n= (f[0] \xe2\x88\x92 f[1]) (g[2] \xe2\x88\x92 g[3]) + (f[2] \xe2\x88\x92 f[3]) (g[0] \xe2\x88\x92 g[1]) .\n

\n

如果我们让f\xe2\x80\xb2 = [f[0] + f[1], f[2] + f[3]]和g\xe2\x80\xb2 = [g[0] + g[1], g[2] + g[3]]，那么前两个量是[f\xe2\x80\xb2[0] g\xe2\x80\xb2[0] + g\xe2\x80\xb2[1] g\xe2\x80\xb2[1], f\xe2\x80\xb2[0] g\xe2\x80\xb2[1] + f\xe2\x80\xb2[1] g\xe2\x80\xb2[0]]，这是同样的问题，但大小只有一半。后两个数量也是如此。终于我们可以恢复了

\n

x = f[0] g[0] + f[1] g[1] + f[2] g[2] + f[3] g[3]\ny = f[0] g[1] + f[1] g[0] + f[2] g[3] + f[3] g[2]\n

\n

fromx + y和x \xe2\x88\x92 yasx = ((x + y) + (x \xe2\x88\x92 y))/2和y = ((x + y) \xe2\x88\x92 (x \xe2\x88\x92 y))/2（对于所有其他对也是如此）。（请注意，Kache\xe2\x80\x99s 代码将除法推迟到最后，以便它可以重用相同的转换。）

\n

Answer 2

为什么异或和是二进卷积

\n

将输入数组表示为a。

\n

构造一个数组b，使得b[i]=a[0]\xe2\x8a\x95a[1]\xe2\x8a\x95...\xe2\x8a\x95a[i]. 然后可以构造一个列表M，代表其中具有值的M[i]元素的数量。请注意，添加了一些零填充以使 M 的长度成为 2 的幂。bi

\n

然后考虑二元（XOR）卷积。定义是（取自该问题的图片）\xef\xbc\x9a\n

\n

M考虑在和之间进行二元卷积M，即N=M*M其中*代表二元卷积。然后是所有这些的N[i]总和。M[j]M[k](j,k)j\xe2\x8a\x95k=i

\n

考虑每个子序列xor(a[p:q])，我们有xor(a[p:q])=b[p]\xe2\x8a\x95b[q]。对于每个整数i，异或结果相等的所有连续子序列都i可以转换为这种形式（i=xor(a[p:q])=b[p]\xe2\x8a\x95b[q]）。b[p]我们进一步根据和的值对这一系列子序列进行分组b[q]，例如，如果xor(a[p1:q1])=xor(a[p2,q2])=i和 如果b[p1]=b[p2],b[q1]=b[q2]，这两个子序列将被分组在同一个子组中。考虑子组(j,k)，其中子序列可以用形式 表示i=xor(a[p\':q\'])=b[p\']\xe2\x8a\x95b[q\'], b[p\']=j, b[q\']=k，该子组中子序列的数量(j,k)为M[j]M[k]（回想一下，它代表其中具有值 的M[i]元素的数量）。的数列也是如此。biN[i]a[p:q]xor(a[p:q])=i

\n

然而，由于a[p:q]和a[q:p]相同，我们对每个子序列计数两次。所以N[i]是“异或得到 i 的连续子序列数”的两倍。

\n

使用FWHT计算卷积

\n

所以现在我们需要的是计算N=M*M，根据二元（XOR）卷积定理（参见这里的证明），我们可以先进行计算H(N)=H(M)\xc3\x97H(M)。由于H是内卷性的（参见wiki），只需再次N申请H即可H(N)。

\n

代码分析

\n

在本节中，我将分析@Kache提供的代码。

\n

事实上，b是 accumulate([0] + seq, xor)。使用histogram = Counter(accumulate([0] + seq, xor))，我们可以获得 的字典{possible_value_in_b: num_of_occurrence}。然后下一行，histogram = [histogram[value] for value in range(next_pow2)]这是M上面提到的添加了填充的内容。

\n

然后histogram = [x * x for x in fwht(histogram)]，所以现在直方图是H(N)。并histogram = [y // next_pow2 for y in fwht(histogram)]充当逆变换。

\n

这就是histogram = [y // next_pow2 for y in fwht(histogram)]要做的。

\n

消除histogram[0] -= len(seq) + 1这一事实的影响a[p:p]=0。并histogram = [y // 2 for y in histogram]避免计数两次（如前所述，分别N[i]计数a[p:q]和a[q:p]）。

\n