Odd Bit Array

4.5

2 votes
2D dynamic programming, Algorithms, Dynamic Programming
Problem

You are given an array A of N integers. A partitioning of the array A is the splitting of A into one or more non-empty contiguous subarrays such that each element of A belongs to exactly one of these subarrays.

Find the number of ways to partition A such that the Bitwise XOR of elements within each subarray has an odd number of set bits (i.e., 1s). Since the answer may be large, output the answer modulo 109+7.

Input format

  • The first line of input contains an integer T denoting the number of test cases.
  • The first line of each test case contains an integer N.
  • The second line of each test case contains N space-separated integers A1,A2,,AN.

Output format

For each test case, print the answer in a separate line.

Constraints

1T101N1050Ai109

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1 - The array can be partitioned as follows

  • [1,6,10]

For test case 2 - The array can be partitioned as follows

  • [1],[4,6],[8],[8]
  • [1],[4,6,8,8]
  • [1],[4],[6,8],[8]
  • [1,4,6,8],[8]

 

Editor Image

?