ODDBIN - Editorial

dec10
editorial
medium
oddbin

#1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

Notation

--------

Let C(n,r) represent the binomial coefficient of choosing r items out of n.

Let BitSet(n) = { i | 2^i is used in the binary representation of n }. Bitset(5) = {0, 2} since 5 = 1 + 4 = 2^0 + 2^2.

Let H(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am (the ai and m are as given in input)

Let G(x) = H(x) modulo 2. (i.e., coefficients of H reduced modulo 2)

Let #(A) represent the cardinality of A for a finite set A.

Let S = {1, 2, …, m} (the m is as given in input)

Let F(s) = Intersection { BitSet(ai) | i belongs to s }, where s is a subset of S.

Let T = {0, 1, …, 59}

Let N(t) = SUM (i belongs to t) { 2^i } where t is a subset of T. N( {0,2,3} ) = 2^0 + 2^2 + 2^3 = 13.

We say p is “present” in G(x) to mean that the coefficient of x^p in G(x) is 1.

L(t) = { i | t is a subset of Bitset(ai) }

Observation 1

-------------

For n>0, 0 <= r <= n, C(n,r) is odd if and only if BitSet® is a subset of Bitset(n).

Proof

-----

Let us compute (1+x)^n where the coefficients are reduced modulo ‘2’. Then, the terms of (1+x)^n correspond to the odd coefficients of

C(n,r). For example (1+x)^2 = 1 + x^2 (modulo 2), indicating that C(2,0) and C(2,2) are odd while C(2,1) is not.

a) (1+x)^(2^k) = 1 + x^(2^k) by induction.

b) Let n = 2^b1 + 2^b2 + … + 2^bk where 0<= b1 < b2 < b3 … < bk. Then, (1+x)^n = Product(1<=i<=k){(1+x)^(2^bi)}

= SUM ( x^p ) where BitSet§ is a subset of BitSet(n).

From the above, it should be clear that the coefficient of x^r modulo 2 is ‘1’ (and hence odd) if and only if BitSet® is a subset of
BitSet(n).

Observation 2

-------------

G(x) = SUM {x^p} where p satisfies the following condition: #{ i | Bitset§ is a subset of Bitset(ai) } is odd.

Put another way: if t is a subset of T, then N(t) is present in G(x) if and only if #L(t) is odd.

Proof

-----

This is rather trivial, since (1+x)^ai contributes x^p to G(x) if and only if BitSet§ is a subset of BitSet(ai). Since x^p has coefficient 1 if and only if an odd number of (1+x)^ai contribute x^p to G(x), the observation follows.

Observation 3

-------------

(1-2)^n = (-1)^n = SUM ( 0 <= r <= n ) { (-1)^r * C(n,r) * 2^r }

Hence, 1 - (-1)^n = SUM ( 1 <= r <= n ) { (-1)^(r+1) * C(n,r) * 2^r }

Note that 1 - (-1)^n = 0 if n is even, and 2 if n is odd.

Observation 4

-------------

If t is a subset of T, then 2*x = SUM ( s is a non empty subset of L(t)) { (-1)^(#(s)+1) * 2^#(s) } where x = 1 if N(t) is present in G(x) and 0 otherwise.

Proof

-----

Another way of looking at Observation 3 is: 1 - (-1)^#(B) = SUM ( b is a non empty subset of B ) { (-1)^(#(b)+1) * 2^#(b) } where B is a finite set. (Note how C(#(B),r) in the summand is replaced by r-element subsets of B in the summation index (and unity in the summand))

Now, substitute L(t) for B and s for b in the above to obtain 1 - (-1)^#L(t) = 2 * x Since x = 1(resp. 0) if #L(t) is odd(resp. even) and N(t) is present in G(x) if and only if #L(t) is odd, the result follows.

Observation 5

-------------

“s is a non empty subset of L(t)” if and only if “s is a non empty subset of S, t is a subset of F(s)”

Observation 6

-------------

Adding both sides of observation 4 over all possible t and using Observation 5, we get 2 * (number of odd coefficients of G(x)) = SUM (s is a non empty subset of S, t is a subset of F(s)) { (-1)^(1+#(s)) * 2^#(s) } or, after eliminating t, 2 * (number of odd coefficients of G(x)) = SUM (s is a non empty subset of S) { (-1)^(1+#(s)) * 2^(#(s) + #F(s)) }

Note that we used #{t | t is a subset of F(s)} = 2^#F(s)

or, W(G(x)) = W(H(x)) = SUM (s is a non empty subset of S) { (-1)^(1+#(s)) * 2^(#(s) + #F(s) - 1) }

The algorithm

-------------

The above observations make it simple enough to compute the desired answer.

We just loop over all possible non empty subsets s of S, and for each s, find #F(s) and compute the sum.

We can use 64 bit unsigned integers to store BitSet(ai) and the fact that unsigned long long additions are performed modulo 2^64 to compute

F(s) fast enough and not worry about overflow of the intermediate sum.

Complexity of this algorithm is O(2^m) (using Dynamic Programming on F(s) computation and bitwise AND for set intersection) per case.

For mask > 0, (mask representing a subset of S) F[mask] = ai if mask = (1 << i ) = F[mask & (mask-1)] & F [ mask & ~ mask-1)], if bitcount(mask) > = 2

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.