小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; }