Xor Subsequences

4.3

3 votes
Dynamic Programming, C++, 2D dynamic programming, Algorithms
Problem

Given an array  of length . For every index , find the number of distinct non-empty XOR subsequences in the subarray .

Note:

  • based indexing is used.
  • Two subsequences are said to be distinct if the XOR of the elements present in the subsequences is different.
  • A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

Input format

  • First line contains an integer 
  • Next line contains  space-separated integers denoting the array 

Output format

Print  space-separated integers where 'th integer denoting the number of distinct XOR subsequences of subarray .

Constraints

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • For , the only subsequence is  with XOR value .
  • For , there exists distinct XOR subsequence  for which the XOR value is  respectively.
  • Similarly for , there exists distinct XOR subsequence.
  • Similarly for , there exists distinct XOR subsequence.
Editor Image

?