题解 | #小G的LY数对#

这道题很恶心，我们只要对a数组处理一位，对b数组处理一位，如果异或值相同就是只有2位为1，然后我们减去两两重合的数量即可。

但是unordered_map爆了，下面的代码就过了10的点，于是我们要手写一个hash表，就可以愉快地AC了。

#include <bits/stdc++.h>



int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n, m; std::cin >> n >> m;
    std::vector <int> a(n), b(m);
    for(int i = 0; i < n; ++i) std::cin >> a[i];
    for(int i = 0; i < m; ++i) std::cin >> b[i];
    std::unordered_map <int, int> num;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 30; ++j) {
            num[a[i] ^ (1 << j)]++;
        }
    }
    long long ans = 0;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < 30; ++j) {
            ans += num[b[i] ^ (1 << j)];
        }
    }
    std::unordered_map <int, int> temp;
    for(int i = 0; i < n; ++i) num[a[i]]++;
    for(int i = 0; i < m; ++i) ans -= num[b[i]] * 30ll;
    ans >>= 1;
    std::cout << ans << '\n';
    return 0;
}

AC代码：

#include <bits/stdc++.h>


struct Hash_set{
    struct Hash{
        int val, v, nxt;
        Hash() : val(0), v(0), nxt(0) {}
        Hash(int x,int y,int z) {val = x, v = y, nxt = z;}
    };
    const int P = 1e6 + 7;
    int tot;
    std::vector <int> head;
    std::vector <Hash> e;
    Hash_set() : tot(0), head((int)3e6, 0), e((int)3e6) {}
    void insert(int x) {
        int u = x % P;
        for(int i = head[u]; i; i = e[i].nxt) {
            if(e[i].v == x) {
                e[i].val++;
                return ;
            }
        }
        e[++tot] = Hash(1, x, head[u]);
        head[u] = tot;
    }
    long long query(int x){
        long long u = x % P;
        for(int i = head[u]; i; i = e[i].nxt) {
            if(e[i].v == x)
                return e[i].val;
        }
        return 0;
    }
};

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n, m; std::cin >> n >> m;
    std::vector <int> a(n), b(m);
    for(int i = 0; i < n; ++i) std::cin >> a[i];
    for(int i = 0; i < m; ++i) std::cin >> b[i];
    Hash_set T;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 30; ++j) {
            T.insert(a[i] ^ (1 << j));
        }
    }
    long long ans = 0;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < 30; ++j) {
            ans += T.query(b[i] ^ (1 << j));
        }
    }
    Hash_set T1;
    for(int i = 0; i < n; ++i) T1.insert(a[i]);
    for(int i = 0; i < m; ++i) ans -= T1.query(b[i]) * 30ll;
    ans >>= 1;
    std::cout << ans << '\n';
    return 0;
}