ProSet is a classic card game that is played normally with 63 cards. One card has 6 colored dots on it, like below

The rest of the cards are missing some of these 6 dots, but each card has at least 1 dot. Every card in the deck is different. Below are some example valid cards.

A ProSet is a nonempty set of cards such that the total number of each color of dot is even. For example, the above set of 4 cards are a ProSet since there are 2 reds, 4 oranges, 2 greens, 2 blues, 0 yellows, and 2 purples.

Interestingly, any set of 7 cards will contain at least 1 ProSet. Hence, in the actual card game, a set of 7 cards are presented, and the player who finds a ProSet first wins. You can try the game out for yourself here.

Challenge

Given a set of cards, each ProSet card can be assigned a value from 1 to 63 in the following manner: a red dot is worth 1 point, an orange 2 points, yellow 4, green 8, blue 16, purple 32. The sum of the values of each dot on the card is the value of the card.

Input: A list of integers from 1-63, i.e.,

[11,26,35,50]

This list represents the above 4 cards.

Output: The number of valid ProSets, which in this example is 1.

Rules

• This is a code-golf challenge.


• This is also a restricted-complexity challenge, as all valid solutions must be in polynomial time or less in the number of dots (in this case 6) and in the number of cards.

Test Cases

I've created an exponential algorithm to find the correct output for every input here. Again, exponential solutions are not valid submissions. But, you can use this to validate your findings.

Edit

I will address the comments in a bit. But for now, none of the answers have been in polynomial time. It is indeed possible, so here's a hint: binary representation and two s complement.

Moreover, I made a mistake earlier when I said polynomial in solely dots. It needs to be polynomial in dots and cards.

Python 2, 60 bytes

p=[0]
for i in input():p+=[n^i for n in p]
print~-p.count(0)

Try it online!

This generate the powerset from the input (based on this answer), reducing each subset by xor.

The output will be the amount of 0s (0 = all bytes/dots appear an even number of times).
^{In fact the xoring is done instead of the "powerset appending", but the result is the same}

Japt, 8 bytes

à x@!Xr^

Try it here

JavaScript (ES6), 53 bytes

f=
a=>a.map(i=>p.map(j=>n+=p.push(j^=i)&&!j),p=[n=0])&&n

<input oninput=o.textContent=f(this.value.split`,`)><pre id=o>

Loosely based on @Rod's Python answer.

Jelly, 8 bytes

ŒPḊ^/€¬S

A monadic Link. 9 bytes if the empty set is considered a ProSet - ŒPḊ^/€¬S‘ (since reducing an empty list errors).

Try it online!

How?

ŒPḊ^/€¬S - Link: list of integers, L
Ã…Â’P - powerset (of cards)
 Ḋ - dequeue (remove the empty list)
 /€ - reduce €ach with:
 ^ - XOR
 ¬ - NOT (vectorises)
 S - sum

Clojure, 182 166 149 127 bytes

(defn f[k]((frequencies(map(fn[x](reduce #(bit-xor % %2)0 x))(reduce(fn[c n](concat(map #(concat %[n])c)[(list n)]c))'()k)))0))

If I had barfed on the screen, it would've looked better than this

Try it online!

Python 2, 88 bytes

lambda l:~-sum(x<1for x in f(l))
f=lambda l:l and[n^l[0]for n in f(l[1:])]+f(l[1:])or[0]

Try it online!