Xor Subsequences

4.3

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

Given an array A of length N. For every index i, find the number of distinct non-empty XOR subsequences in the subarray A[1,2,....,i].

Note:

  • 1 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 N
  • Next line contains N space-separated integers denoting the array A

Output format

Print N space-separated integers where i'th integer denoting the number of distinct XOR subsequences of subarray A[1,2,....,i].

Constraints

1N,A[i]<210

 

Sample Input
4
1 2 3 4
Sample Output
1 3 4 8
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • For i=1, the only subsequence is [1] with XOR value 1.
  • For i=2, there exists 3 distinct XOR subsequence [1],[2],[1,2] for which the XOR value is 1,2,3 respectively.
  • Similarly for i=3, there exists 4 distinct XOR subsequence.
  • Similarly for i=4, there exists 8 distinct XOR subsequence.
Editor Image

?