Killjee and subsets

★★★★★

4 votes

Medium, Two dimensional

Details

Submissions

Discussion

Editorial

Problem

Killjee is playing with an array a, which has n integers. He is trying to encrypt this array as a single integer.

Let l be the largest number in array a. Then, the code for array a is $\sum_{j=0}^{l} b_j*31^j$ mod $10^9+7$ .

Here, $b_j$ is the size of largest subset of array a whose XOR is equal to j.If there exist no subset of array a whose XOR is j then $b_j = 0$ .

INPUT CONSTRAINTS:

$1 \le n \le 10^4$

$1 \le a_i \le 10^3$

INPUT FORMAT :

First line of input contains a single integer n. Next line contains n space separated integers, elements of array a.

OUTPUT FORMAT :

Print a single integer code of the array a.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Here, $b[0]=3$ as the subset $(1,2,3)$ has xor value equal to 0.

$b[1]$ =2, as the subset $(2,3)$ has xor value equal to 1

$b[2]$ = 2, as the subset $(1,3)$ has xor value equal to 2

$b[3]$ =2, as the subset $(1,2)$ has xor value equal to 3

$b[4]$ = 4, as the subset $(1,2,3,4)$ has xor value equal to 4.

Thus, the answer = $(b[0] \times 31^0) + (b[1] \times 31^1) + (b[2] \times 31^2) + (b[3] \times 31^3) + (b[4] \times 31^4 )$ Modulo $10^9+7$ = $3755653$ .