B. Arpa’s obvious problem and Mehrdad’s terrible solution
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are some beautiful girls in Arpa’s land as mentioned before.
Once Arpa came up with an obvious problem:
Given an array and a number x, count the number of pairs of indices i, j (1 ≤ i < j ≤ n) such that , where is bitwise xor operation (see notes for explanation).
Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.
Input
First line contains two integers n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) — the number of elements in the array and the integer x.
Second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 105) — the elements of the array.
Output
Print a single integer: the answer to the problem.
Examples
input
2 3
1 2
output
1
input
6 1
5 1 2 3 4 1
output
2
Note
In the first sample there is only one pair of i = 1 and j = 2. so the answer is 1.
In the second sample the only two pairs are i = 3, j = 4 (since ) and i = 1, j = 5 (since ).
A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.
题意:一个数组，有n个数，输入一个数x，然后是n个数，判断这n个数中，有多少个异或对，符合ai^aj=x。输出异或对的对数。
题解，直接暴力用x异或数组中的每个值，然后检查数组中是否有这个值即可。
注意异或出来的东西可能很大。
而对比异或值是否出现，可以用数组或map来计数。根据出现次数来判断对数。
要特判自己异或自己等于x的情况，当x=0是出现这种情况
#include<stdio.h>
#include<string.h>
long long n,x,a[1050008],i,b[100008];///a数组用于标记出现的数的次数，b数组用于记录输入的数
int main()///a数组的标记同样可以用map实现，并且因为map无大小限制，因此不用考虑异或之后数值大小，但数组的要必须开的更大
{
while(scanf("%lld%lld",&n,&x)!=EOF)
{
memset(a,0,sizeof(a));
for(i=0; i<n; i++)
{
scanf("%lld",&b[i]);///输入数组中的数
a[b[i]]++;///计数出现次数
}
long long flag=0;///找到的异或组数
for(i=0; i<n; i++)
{
if((x^b[i])!=b[i])
{
flag+=a[(x^b[i])];///正常情况，用x异或正在遍历的数，然后检查得数是否在数组b中，并且加上这个结果出现的次数，就是异或对的数量
}
else///如果x=0时，会出现两个相同的值异或运算之后等于0，此时因为计数面对的是同一个数字，因此自己不能和自己配对，只能是
flag+=a[(x^b[i])]-1;///所有相同数的数量里，减去自己(-1),加上的次数才是自己和其他重复数字的配对数量
}
printf("%lld
",flag/2);///因为从头至尾算重复两遍，所以算出来的组数要除2才是正确组数
}
}