I stumbled upon a problem that can be reduced to the following: given 22-bit masks a1, a2, ..., an (n < 106), calculate d[m] = the number of i such that a[i] is a submask of m (i.e. a[i] & m == a[i]).
The jury solves it like this:
for (int i = 0; i < n; i++) {
d[a[i]]++;
}
for (int i = 0; i < 22; i++) {
for (int mask = 0; mask < (1 << 22); mask++) {
if ((mask & (1 << i)) == 0) {
d[mask | (1 << i)] += d[mask];
}
}
}
I came up with a similar idea while trying to solve the problem myself, but discarded it immediately because I felt like it ought to double-count some submasks. I seem to have managed to convince myself that it doesn't, but I still don't have an intuitive understanding for why this approach works. Is this some kind of a trick that I don't know? Or perhaps somebody could just explain the reasoning behind this solution to me?
Thanks!