(标题忘了)

时间：1500ms

空间：512MB

文件：xor.in / .out

给定数列 $a$ 和整数 $K$，求有多少对整数 $i,j$ 满足 $a_i \space xor \space a_j = K$

输入

第一行，两个整数 $n, K$，$n$ 表示 $a$ 的长度。

第二行，$n$ 个以空格分隔的整数，表示 $a_1, a_2, ... , a_n$

输出

一个整数 $c$，表示有 $c$ 对整数 $i,j$ 满足 $a_i \space xor \space a_j = K$

样例

5 6
1 2 2 4 5

2

数据范围

$n \leq 10^6$

$a_i, k \leq 2^{30}$

nPr Code

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;

ll a[maxn];

int main() {
//	freopen("xor.in", "r", stdin);
//	freopen("xor.out", "w", stdout);
	
	ll n, k;
	scanf("%lld%lld", &n, &k);
	
	for (int i = 0; i < n; i++)
		scanf("%lld", a + i);
		
	sort(a, a + n);
	
	ll tot = 0;
	
	for (int i = 0; i < n; i++)
		tot += upper_bound(a + i, a + n, k ^ a[i]) - lower_bound(a + i, a + n, k ^ a[i]);
		
	printf("%lld", tot);
	
	return 0;
}