题目描述

塔子哥有一个长度为$n$的数组$a$，他想知道有多少对$\{a_i,a_j,a_k,a_l\},(i \lt j \lt k \lt l)$满足$a_i +a_j =a_k⊕a_l$

思路：哈希

给定一个长度为$n$的数组数组$a$，求有多少对$\{a_i,a_j,a_k,a_l\},(i \lt j \lt k \lt l)$满足$a_i +a_j =a_k⊕a_l$

本题很容易想到用四重循环去枚举应当选取哪些数并计算符合要求的对数，但是$n\le 10000$，而这种方法的时间复杂度是$O(N^4)$，显然是不能够满足要求的。

我们可以发现，$i,j,k,l$需要满足严格的大小关系，同时，在$O(N^2)$的处理下，我们可以得到所有对子$a_i+a_j$的值以及$a_k⊕a_l$的值，并通过哈希来存储每个对子出现了多少次。所以我们可以尝试去隔断$a_j$与$a_k$，将数组分为两部分去计算答案。

具体来说，当我们预处理出所有对子$a_k⊕a_l$的值时，我们从小到大枚举$j$，那么剩余的$a_{j+1}$~$a_n$对应的$a_k⊕a_l$已经预处理好了，我们可以再枚举$i(1\le i\lt j)$来计算$a_i+a_j$，而其和所对应的$a_k⊕a_l$已经通过哈希预处理好，直接累加即可。当$j$枚举$+1$前，则需要在预处理中去掉$a_j⊕\{a_{j+1},a_{j+2},...,a_n\}$，这个操作的时间复杂度是$O(N)$的。