algorithm - Inclusion-exclusion in dynamic programming -

there n soldiers (numbered 1 n). each soldier has subset of skills out of m different skills (numbered 1 m). skill-set of army union of skill-sets of constituent soldiers. how many different subsets of soldiers satisfy there have specific skill-set requirement

problem link

according explanation problem reduces finding number of subsets of these numbers or equal required value, req

let f(i) number of numbers j such j or = i.

then answer is
∑i(−1)^popcount(i xor req)(2^f(i)−1) such or req req

please explain above formula , how came

i know no. of ways choose n element (2^n-1) why term (−1)^popcount(i xor req)

please explain algorithm.

after reading editorial , got ac myself, not think easy understand application of "inclusion-exclusion principle" here, problem around codeforces div.1 problem c / d level, example, one: http://codeforces.com/contest/449/problem/d

rewritten version@2016

previous answer messy, try clean , rewrite more readable answer

i going explain why solution works, not how come such solution, think that's more experience.

big picture explanation

first, not on think problem, given a[1..n], solution literally all subsets can produce req

being said, how can find subset can produce x? solution shows, let's define f(i)

let f(i)be number of numbers such j or i = i.

if find hard understand, think physical meaning:

for i, j or i = i iff j can produced take away binary bit 1 away from i

for example, if i = 7, j can 0,1,2...,7; if i=5, j can 0,1,4,5

so, 2^f(i) - 1 indeed # of possible subsets can produce i when or i

hold second here, make sure on above part first.

now if i = req itself? means? subsets counted in 2^f(req)-1? how 2^f(req)-1 related answer want?

we want # of subsets or elements produce req

2^f(req)-1 gives # of subsets or elements or req produce req

can smell 2^f(req)-1 count more need?

think this: there subsets 2^f(req)-1 counts, or elements can produce x x can produced take away binary bit 1 req (see block quote above)

so, have minus 2^f(req)-1, , here comes inclusion-exclusion principle.

let's want minus subsets or elements equal x, req take away 1 binary bit 1

with similar thoughts, find have minus 2^f(x)-1 , possible x, here, remember x numbers req take away 1 binary bit 1

but then, going minus more should, because different x may share same y, y req take away two binary bit 1, or y x take away 1 binary bit 1, suppose remove 1 time each y 2^f(req)-1, in process of minus 2^f(x)-1, have minus multiple times y!

by inclusion-exclusion principle, have add them back...let's have little summary here:

what want 2^f(req)-1 - 2^f(x)-1 + 2^f(y)-1 ... x set of numbers equal req remove 1 binary bit 1, y set of numbers equal req remove 2 binary bit 1 (or x remove 1 binary bit 1)

can see pattern here? yes, that's -1^popcount() part in formula

for i <= req, every bit of i either same req or 0, i xor req equal req - i(remove 1-bit of i), so popcount(i xor req) indeed gives # of binary bit 1 removed req in order i

combined whole story, formula formed: sum (-1)^popcount(i xor req) * (2^f(i) - 1) i such i or req = req

dp calculate f(i)

for(int i=0;i<20;i++)        for(int j=0; j<=(1<<20); j++) {             if(j&(1<<i)) {                 f[j] += f[j^(1<<i)];             }        }

here dp part calculate f(i)

note base on following recurrence relation:

f(i) = i + f(some j remove bit 1)

so, f(i) = 1 + f(i xor (1 << j)) if i's j-th bit 1

note i xor (1<<j) must smaller i, hence dp order.