На олимпиаде Казахстана прошлого года была задача "Количество совместимых чисел", которая сводится к такой: даны 22-битные маски a₁, a₂, ..., a_n (n < 10⁶), нужно посчитать d[m] — количество таких i, что a[i] является подмаской m (т.е. a[i] & m == a[i]).

Официальное решение решает эту задачу так:

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];
		}
	}
}

Пытаясь решить эту задачу самостоятельно, я дошёл до этой идеи, но сразу отбросил, потому что мне показалось очевидным, что она какие-нибудь подмаски будет считать несколько раз. Сейчас я вроде бы почти убедил себя, что этого не происходит, но у всё ещё меня нет интуитивного понимания того, почему это должно работать. Может, это какой-то известный трюк, которого я не знаю? Или может просто кто-нибудь может объяснить логику этого подхода?

Спасибо!