XOR
closed account (ywUDz8AR)
For a given sequence of positive integers A1,A2,…,AN, you are supposed to find the number of triples (i,j,k) such that 1≤i<j≤k≤N and
Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,
where ⊕ denotes bitwise XOR.
Example Input
1
3
5 2 7
Example Output
2
Explanation
The triples are (1,3,3), since 5⊕2=7, and (1,2,3), since 5=2⊕7.
Constraints
1≤T≤10
2≤N≤10^5
1≤Ai≤10^6 for each valid i
Can someone explain me the approach please? thanks!
Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,
where ⊕ denotes bitwise XOR.
Example Input
1
3
5 2 7
Example Output
2
Explanation
The triples are (1,3,3), since 5⊕2=7, and (1,2,3), since 5=2⊕7.
Constraints
1≤T≤10
2≤N≤10^5
1≤Ai≤10^6 for each valid i
Can someone explain me the approach please? thanks!
This sounds like a codechef problem. Since those problems are supposed to be done on your own, most people here won't be willing to help.
It's also true that many of the professional programmers here don't think highly of code chef. This thread explains some of it:
http://www.cplusplus.com/forum/lounge/257301/
It's also true that many of the professional programmers here don't think highly of code chef. This thread explains some of it:
http://www.cplusplus.com/forum/lounge/257301/
Do you know how to do truth tables? So, there's 5 = 101 and 2 = 010 so
|
|
Last edited on
if(a == b) means a ^ b = 0 and a ^ (b ^ c) = (a ^ b) ^c. use this two property. Complete solution is available here https://whitefox-89ea6.firebaseapp.com/
Topic archived. No new replies allowed.