Inclusion-exclusion in dynamic programming

Question

There are N soldiers (numbered from 1 to N). Each soldier has some subset of skills out of M different skills (numbered from 1 to M). The skill-set of an army is the union of skill-sets of its constituent soldiers. How many different subsets of soldiers satisfy are there which have specific skill-set requirement

Problem Link

According to the Explanation problem reduces to finding the number of subsets of these numbers whose OR is exactly equal to the required value, say req

Let f(i) be the number of numbers j such that j OR i = i.

Then the answer is
∑i(−1)^popcount(i xor req)(2^f(i)−1) for all i such that i OR req is req

Please Explain the above formula and How it came

I know No. of ways to choose N element is (2^n-1) but why this term (−1)^popcount(i xor req)

Please Explain the algorithm.

Answer 1

This is inclusion exclusion.

Let's examine a simplified version of the problem. Assume you had 2 sets A, B. Assume you are looking for the size of the subset that has exactly 1 element.

First, you calculate |A| + |B|. But in here, you counted the size of the intersection | A [intersection] B| twice, both in |A| and in |B|, so you reduce it and get |A| + |B| - |A [intersection] B|.

Similarly for 3 sets, you first add the sizes of all sets: |A| + |B| + |C|.
Then, you reduce all "connections" between two sets |A [intersection] B|, |A [intersection] C|, |B [intersection] C|. But now, you removed too much elements, you also removed the elements in |A [intersection] B [intersection] C|. To overcome it, you add this size.

So, generalizing it - you get for n sets, and m desired properties:

#of items with m properties: 
E(m) = sum { (-1)^(r-m) * Choose(r,m) * W(r) } 
Where: 
W(r) = summation of all intersections of size i, or formally:
W(r) = sum { W(p_k_1,...,p_k_r) | 1<=k_1<k_2<...<k_r<=n } 
W(pk1,...,pkr) = |X_k1 [intersection] X_k2 [intersection] .... [intersection] X_kr|

This explains how the (-1)^x comes to play, we repeatidly include (add) and exclude (reduce) sizes. (-1)^x allows us to "automatically" reduce/add for every element in the summation.

---

As you said, popcount(i xor req) is counting the number of "up" bits in the representation of i^req. That means, popcount() is effectively your index i at the above formula, and your sets are: X_i = all soldiers with required property i.
This means if k = popcount(i XOR req), i got exactly k "required" properties, and belongs in the above summation to the value when r=k, and thus the property add/substract depends on the value of (-1)^k = (-1)^popcount(i XOR req)