Учитывая набор, найдите XOR XOR всех подмножеств

Question

Я искал в сети. Решение находится в link.

Дело, которое я не мог получить было:

Рассмотрим n-й элемент, он может быть включен во всех подмножеств оставшихся (N-1) элементов. Число подмножеств для (n-1) элементов равно 2^(n-1).

Что он пытается сказать?

Answer 1

Got it. Для того, чтобы подсчитать, сколько раз элемент приходит в подмножеств множества ... фиксируем элемент и начать подсчет числа подмножеств длины:

1 -> 1 
2 ->NC1 
3 ->NC2 
. 
. 
. 
N ->NC(N-1) 

Общее количество раз элемент появляется в подмножеств заданного set = общее число подмножеств, содержащих элемент = 1 + NC1 + NC2 + NC3 + ..... + NC (N-1) = 2^(N-1).