思路：哈希

给定一个长度为$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)$的。

这样，就将原来的$O(N^4)$算法降到了$O(N^2)$

代码

C++

AC

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

const long long mod = 1e9 + 7;
const int maxn = 1e4 + 10;
int n;
int a[maxn];
int cnt[300];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n;  // 输入整数n
    for (int i = 1; i <= n; ++i) cin >> a[i];  // 输入n个整数，存储在数组a中
    for (int i = 2; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            cnt[a[i] ^ a[j]]++;  // 计算a[i]和a[j]异或结果出现的次数
        }
    }
    long long ans = 0;
    for (int j = 2; j <= n; ++j) {
        for (int i = j + 1; i <= n; ++i) cnt[a[i] ^ a[j]]--;
        for (int i = 1; i < j; ++i) {
            ans += cnt[a[i] + a[j]];  // 统计a[i]+a[j]出现的次数，并累加到答案ans中
            ans %= mod;  // 取答案对1e9+7取模
        }
    }
    cout << ans;  // 输出答案

    return 0;
}

python

n = int(input())  # 输入整数n
a = [0] + list(map(int, input().split()))  # 在a的最前面添加一个0，然后输入n个整数，存储在列表a中

mod = 10**9 + 7
maxn = 10**4 + 10
cnt = [0] * 300

for i in range(2, n + 1):
    for j in range(i + 1, n + 1):
        cnt[a[i] ^ a[j]] += 1  # 计算a[i]和a[j]异或结果出现的次数

ans = 0
for j in range(2, n + 1):
    for i in range(j + 1, n + 1):
        cnt[a[i] ^ a[j]] -= 1
    for i in range(1, j):
        ans += cnt[a[i] + a[j]]  # 统计a[i]+a[j]出现的次数，并累加到答案ans中
        ans %= mod  # 取答案对10^9+7取模

print(ans)  # 输出答案

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int mod = 1000000007;  // 定义常数 mod，用于取模运算
        final int maxn = 10010;  // 定义最大数组长度
        int n = scanner.nextInt();  // 输入整数 n，表示数组长度
        int[] a = new int[maxn];  // 创建整数数组 a，用于存储输入的数据
        int[] cnt = new int[300];  // 创建整数数组 cnt，用于存储计数结果

        for (int i = 1; i <= n; ++i) {
            a[i] = scanner.nextInt();  // 输入 n 个整数，存储在数组 a 中
        }

        for (int i = 2; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                cnt[a[i] ^ a[j]]++;  // 计算 a[i] 和 a[j] 异或结果出现的次数
            }
        }

        long ans = 0;
        for (int j = 2; j <= n; ++j) {
            for (int i = j + 1; i <= n; ++i) {
                cnt[a[i] ^ a[j]]--;
            }
            for (int i = 1; i < j; ++i) {
                ans += cnt[a[i] + a[j]];  // 统计 a[i]+a[j] 出现的次数，并累加到答案 ans 中
                ans %= mod;  // 取答案对 mod 取模
            }
        }

        System.out.println(ans);  // 输出答案
    }
}

题目描述

小红有一个长度为$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$

答案可能太大，请对$10^9+7$取模后再输出。

输出描述

第一行一个正整数$n$。 第二行$n$个正整数$a_i$

$1 \leq n \leq 10^4$

$1 \leq a_i \leq 100$

输出描述

一个整数，表示对$10^9+7$取模后的答案。

样例

输入

5
4 5 5 1 8

输出

2

说明

满足要求的四元组有$(1,2,4,5)$和$(1,3,4,5)$，即：$4+5=1⊕8=9$