Arpa’s obvious problem and Mehrdad’s terrible solution codeforces problem/742/ 异或

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
inputCopy
2 3
1 2
outputCopy
1
inputCopy
6 1
5 1 2 3 4 1
outputCopy
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.

由于ACM要对英语掌握熟练，但是我的英语很菜，比小学生还辣鸡，so，我预计以后的题解尽量用一大堆拼写错误，语法错误的英语写。希望能对英语有所帮助。

the problem’s link

http://codeforces.com/problemset/problem/742/B

what’s the problem meaning

the first row give you two-number ‘n’ , ‘x’ . the ‘n’ means the second row there will be N number , the question is how many pair of number can be ai ^ aj = x .

data range

n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105)
a1, a2, …, an (1 ≤ ai ≤ 105)
i, j (1 ≤ i < j ≤ n)

my idea

**what is Exclusive or 异或’^’ **
when binary ( 二进制) , if the two number is same , their ‘Exclusive or’（异或） is ‘1’
else is ‘0’.
for example
1 ^ 1 = 0 ; 1 ^ 0 = 1; 0 ^ 1 = 1; 0 ^ 0 = 0;

**the properties’s（性质） of Exclusive or 异或’^’ **

a ^ b = c Is equivalent to（等价于） b ^ a = c (交换律)Commutative law
is also equivalent to（等价于） a ^ c = b Is equivalent to（等价于）b ^ c = a It is a special property

other properties

1. a ⊕ a = 0

2. a ⊕ b = b ⊕ a

3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;

4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.

5. a ⊕ b ⊕ a = b.

use the 4th property , we can use every number ^ x , check the number you get if it was been in the previous number . if yes , ans++. but if ai ^ x = ai ,you should notice that , you can’t count it twice .
use the quantity of the number you get to multiply（乘）the quantity of the previous number ,then ans is half of it .

AC code

#include<cstdio>
long long b[200005];
int main(){
long long n,x,d;
long long ans = 0;
scanf("%lld %lld",&n,&x);
for(int i = 1;i <= n;i++){
	scanf("%d",&d);
	b[d]++;
	}
	for(int i = 1;i <= 200001;i++){
		if(b[i]!=0){
			if((i^x)==i)ans-=b[i];
			ans+=(b[i^x]*b[i]);
		}
	}
		printf("%lld\n",ans/2);
return 0;
}