HELP Count Sub-sequences

Revision en2, by ShashwatS1, 2021-09-09 18:37:53

You are given the following :-

— An array A of length N
— An integer X

Task

Determine the number of sub-sequences of Array A such that the following condition is satisfied.

— If i1,i2....ik is the indices in the sub-sequence, then ( A[i1] ^ A[i2] ^.....^A[ik] ) & X =0, where ^ represents Bitwise XOR and & represent Bitwise AND operator.

Since, the number of sub-sequences can be large enough, output it modulo 10^9+7.

Example:-

Assumptions

  • N = 4
  • X = 7
  • A[] = [5,2,7,6]

Output:-
2 , one is [5,2,7] another Empty sub-sequence.

Constraints

  • 1<= N <= 1000
  • 1<= X <= 1000
  • 0<= A[i] <= 1000

Sample Input:-
3
1
5 7 1

Sample Output:-
4

Tags #bitwise

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ShashwatS1 2021-09-09 18:38:58 8
en2 English ShashwatS1 2021-09-09 18:37:53 1 Tiny change: '.\n\n\n\n #### Cons' -> '.\n\n\n\n #### Cons'
en1 English ShashwatS1 2021-09-09 18:34:37 877 Initial revision (published)