Description
定义一个数 $S$ 在二进制下数值为 1 的位数的个数为 $cnt(S)$。
现在给出你两组数 $\{a_1,a_2,…,a_n\}$ 和 $\{b_1,b_2,…,b_m\}$。
请你求出 $\sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} [cnt(a_i ⊕ b_j) = 2]$ 的值。
Solution
考虑一个比较暴力的做法：先把 $b_j$ 放进哈希表里，然后暴力枚举 $a_i$ 改了哪两位，再到哈希表里找，统计个数和即可。
但这样有一个 900 的常数，想要卡过去有点难度，考虑进行卡常。
优化：把 $b_j$ 改一位的结果丢进哈希表里，然后暴力枚举 $a_i$ 改了哪一位，再到哈希表里找，统计个数和，最后减去 $a_i = b_j$ 的情况再除 2 即可。
这样的话常数大概就是 30 + 30 = 60 了，比较容易卡过去。
我写的是离散化，复杂度多了一个 $\log$，开 O2 后卡过去了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| #pragma GCC optimize(2)
#include <cstdio>
#define maxN 3000010
int pow[50];
int f[maxN], g[maxN];
int a[maxN], b[maxN], c[maxN], d[maxN];
int read ()
{
int x = 0;
char c = getchar();
while(c < '0' || c > '9')
{
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
void px (int p[], int l, int r)
{
int x = l, y = r, mid = p[(l + r) >> 1];
while(x <= y)
{
while(p[x] < mid)
{
x++;
}
while(p[y] > mid)
{
y--;
}
if(x <= y)
{
int t = p[x];
p[x] = p[y];
p[y] = t;
x++;
y--;
}
}
if(l < y)
{
px(p, l, y);
}
if(x < r)
{
px(p, x, r);
}
}
int find (int x)
{
int l = 1, r = c[0];
while(l < r)
{
int mid = (l + r) >> 1;
if(c[mid] < x)
{
l = mid + 1;
}
else
{
r = mid;
}
}
return c[l] != x ? 0 : l;
}
int main ()
{
int n = 0, m = 0;
n = read();
m = read();
for(int i = 1;i <= 30; i++)
{
pow[i] = (1 << (i - 1));
}
for(register int i = 1;i <= n; i++)
{
a[i] = f[i] = read();
}
for(register int i = 1;i <= m; i++)
{
g[i] = read();
for(register int j = 1;j <= 30; j++)
{
b[++b[0]] = (g[i] ^ pow[j]);
}
}
px(b, 1, b[0]);
c[++c[0]] = b[1];
d[c[0]] = 1;
for(register int i = 2;i <= b[0]; i++)
{
if(b[i] != b[i - 1])
{
c[++c[0]] = b[i];
}
d[c[0]]++;
}
long long Ans = 0;
for(register int i = 1;i <= n; i++)
{
for(register int j = 1;j <= 30; j++)
{
Ans += d[find(a[i] ^ pow[j])];
}
}
px(f, 1, n);
px(g, 1, m);
int j = 1;
int cnt = 0;
for(register int i = 1;i <= n; i++)
{
cnt = 1;
while(f[i] == f[i + 1] && i + 1 <= n)
{
i++;
cnt++;
}
while(g[j] < f[i] && j <= m)
{
j++;
}
while(g[j] == f[i] && j <= m)
{
Ans -= 30 * cnt;
j++;
}
if(j > m)
{
break;
}
}
printf("%lld", Ans / 2);
return 0;
}
|