小G的LY数对

题目链接:nowcoder 218399

到主站看:https://blog.csdn.net/weixin_43346722/article/details/114853824

题目大意

有两个数组,要你各选一个数,使它们异或的值在二进制中恰好有两位是 1。
问你有多少种选法。

思路

我们看到异或,考虑从位数处理。

看到只要两位不同,我们可以考虑用这一个方法(类似折半?)。
把两边每个数对于每一位取反得到的数互相匹配,看有多少个相同的且在两边的。
那直接匹配相同我们可以用哈希表来实现。

那接着我们就会发现一个问题,就是可以能两个数取反的位置都是相同的,然后它们这样相同了,那它不能算,而我们会算上。
那我们考虑容斥,把这种情况减去。
因为取反的是同一位,那再取反就说明等于没取反,那我们就只用找两边有多少对相同的,把答案减去这个个数 即可。
要乘 是因为每一位都可以这样,就每对有三十次要减去。

然后就好了。

代码

#include<cstdio>
#include<cstring>
#define mo 1000007
#define ll long long

using namespace std;

struct Hash {
    int x, to, nxt;
}e[3000007];
int le[3000007], KK;
ll n, m, a[500001], b[500001];
ll ans;

void Hash_push(int now) {//哈希操作
    ll pl = now % mo;
    for (int i = le[pl]; i; i = e[i].nxt)
        if (e[i].to == now) {
            e[i].x++;
            return ;
        }
    e[++KK] = (Hash){1, now, le[pl]}; le[pl] = KK;
}

ll Hash_ask(ll now) {
    ll pl = now % mo;
    for (int i = le[pl]; i; i = e[i].nxt)
        if (e[i].to == now) return e[i].x;
    return 0;
}

int main() {
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%lld", &b[i]);

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 30; j++)
            Hash_push(a[i] ^ (1 << j));//插入一边异或一个位置

    for (int i = 1; i <= m; i++)
        for (int j = 0; j < 30; j++)
            ans += 1ll * Hash_ask(b[i] ^ (1 << j));//寻找另一边也异或一个位置和是否有前面一边异或一个位置一样的

    memset(le, 0, sizeof(le));//去掉异或的位置是同一个位置的情况
    memset(e, 0, sizeof(e));
    KK = 0;
    for (int j = 1; j <= n; j++)
        Hash_push(a[j]);
    for (int j = 1; j <= m; j++)
        ans -= Hash_ask(b[j]) * 30ll;

    printf("%lld", ans >> 1);

    return 0;
}