Xor Subsequences

★★★★★

4.3

3 votes

Dynamic Programming, C++, 2D dynamic programming, Algorithms

Details

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

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

$1 \le N, A[i] < 2^{10}$

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.