I stumbled upon a problem that can be reduced to the following: given 22-bit masks a₁, a₂, ..., a_n (n < 10⁶), 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!