BADXOR - Bad XOR
You are given an array A of N elements. Also you are given another array B of M elements. Any subset (i1, i2, i3 ... ip) is bad IFF (Ai1 ⊕ Ai2 ⊕ ... ⊕ Aip) equals any value of B. (⊕ means Bitwise XOR, which can be found with ^ syntax in popular programming languages.) Now your job is to find the number of good subsets. Empty subset has XOR value of 0.
Input
The first line of input denotes the number of test cases T (1 ≤ T ≤ 20). The first line of each test case contains two integers N and M (0 ≤ N, M ≤ 1000). The next line contains N integers of the array A (0 ≤ Ai ≤ 1000). The next line contains M integers of the array B (0 ≤ Bi ≤ 1000). You can assume that each element of array B will be unique.
Output
For each case, print the case number and the total numbers of good subsets in a line. As the result can be very big, output it modulo 100000007.
Example
Input: 2 2 3 1 2 0 1 2 1 3 1 0 1 2 Output: Case 1: 1 Case 2: 0
Problem Setter: Nafis Sadique, Special Thanks: Ahmad Faiyaz
hide comments
mammadbastar:
2019-02-14 13:55:43
ba tashakor az ostad azizam kianoosh.a |
|
ankitpriyarup:
2018-12-24 10:36:17
Nice question took me time to crack |
|
pallindromeguy:
2018-07-12 23:53:46
Make sure your dp array is of size 1024, gave WA on 1007. And keep in mind the sample output. Rest is easy ;) |
|
pk845:
2018-07-12 19:27:55
is there is new line after every test cases?
|
|
manktbvh11:
2018-06-06 17:33:50
carefully with mod . 1e8+7 not 1e9+7 . lmaoez
|
|
sherlock11:
2018-06-06 08:19:40
check case when n=0..........costed me plenty of wrong answers and lots of hour of remorse....... Last edit: 2018-06-06 08:19:59 |
|
aman_sachin200:
2018-05-24 21:30:07
Read the modulo and the output format carefully!Cost me 4 WAs :( |
|
bluejam:
2018-05-21 05:00:41
Corner Case n=0
|
|
pranjal_27:
2018-01-02 10:15:38
Just do not try Spoj Toolkit for this question .... Most of the test cases are wrong ... Keep belive in yourself ... :)
|
|
kspoj:
2017-12-16 07:02:10
changed table size to [n+1][2000] and it got accepted :P
|
Added by: | Faiyaz |
Date: | 2013-12-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |