解题思路
本题要求统计下标四元组 (i,j,k,l) 满足 1≤i<j<k<l≤n 且 ci+cj=ck⊕cl 的数量。直接四重循环枚举的时间复杂度为 O(n4),无法承受 n≤104 的数据范围。
注意到序列中的值不超过 100,因此 ci+cj 的最大值为 200,ck⊕cl 的最大值不超过 127(因为 100 的二进制为 1100100,异或结果不超过 127)。我们可以利用元素大小关系的对称性,通过“隔断” j 与 k 来降低复杂度:
- 预处理右侧异或值:将数组从 j+1 到 n 的部分视为右侧候选 k,l。我们维护一个计数数组
cnt,cnt[x] 表示在当前 j 的右侧(即 j+1≤k<l≤n)有多少对 (k,l) 满足 ck⊕cl=x。初始时令 j=2,此时右侧为下标 3∼n,枚举所有 p,q 满足 2<p<q≤n(实际上是 p 从 j+1 到 n,q 从 p+1 到 n)并把对应异或值放入 cnt 中。
- 枚举 j 并累加答案:我们从 j=2 扫描到 n−1(因为 k,l 至少需要两个位置)。对于当前的 j,右侧
cnt 已经存储了所有满足 k>j 的 (k,l) 对。此时枚举所有 i 满足 1≤i<j,计算和 s=ci+cj,然后答案累加 cnt[s],并对 109+7 取模。
- 移动 j 并更新
cnt:当 j 向右移动至 j+1 时,原来在右侧的 cj 现在变为左侧元素,因此我们需要从 cnt 中除去所有包含 cj 的 (j,l) 对(l 从 j+1 到 n)。具体操作:对于所有 i=j+1∼n,我们将 cnt[c_j ^ c_i] 的值减 1。这样 cnt 就正确地表示了新 j 右侧的异或值计数。