SUBXOR - SubXor
A straightforward question. Given an array of positive integers you have to print the number of subarrays whose XOR is less than K. Subarrays are defined as a sequence of continuous elements Ai, Ai+1 ... Aj . XOR of a subarray is defined as Ai ^ Ai+1 ^ ... ^ Aj. Symbol ^ is Exclusive Or. You can read more about it here: en.wikipedia.org/wiki/Exclusive_or.
Input
First line contains T, the number of test cases. Each of the test case consists of N and K in one line, followed by N space separated integers in next line.
Output
For each test case, print the required answer.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ K ≤ 10^6
Sum of N over all testcases will not exceed 10^5.
Sample Input:
1 5 2 4 1 3 2 7
Sample Output:
3
Explanation:
Only subarrays satisfying the conditions are [1], [1, 3, 2] and [3, 2].
Problem Setter: Lalit Kundu
hide comments
ng_1997:
2022-04-17 21:54:23
for those who are getting WA, check for the arrays where all the elements are same. |
|
lovro_nidogon1:
2020-08-24 14:19:57
A skudiba, skidibapiba |
|
awesomeamul:
2020-03-23 14:40:34
please use long long for answer
|
|
shubham97361:
2019-07-30 23:15:36
tough to implement. |
|
aqua4:
2018-08-18 12:50:25
Nice problem! Last edit: 2018-08-18 12:56:17 |
|
sanyam123:
2018-01-28 16:09:18
I think there is some bug with time limits firstly same problem on codechef is getting AC(1.83 sec) with time limit of 2 seconds . Here solution with 1.54s is getting AC so what's the point of stating time limit of 1 sec. @ darkshadows |
|
ibrahim5253:
2017-11-10 20:18:29
Don't forget nothing. |
|
Shubham Sinha:
2016-06-25 10:37:17
make the number of bits in all the numbers that u will be processing equal which can be done by adding leading zeros for example make the number of bits in all numbers equal to 20 and then proceed, this will avoid any wrong answers. |
|
akhil3sh:
2016-03-03 11:24:35
use long long for answer |
|
Gaurav Arora:
2016-02-06 17:55:18
I had to use fast input using getchar_unlocked to avoid TLE
|
Added by: | darkshadows |
Date: | 2014-01-26 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |