XOR
-
c
умма массива определяется как побитовое
XOR
всех его элементов или
0
, если массив пуст.
Например,
XOR
-сумма массива
[2,5,6]
равна
2 XOR 5 XOR 6 = 1.
Для заданного массива
nums
, верните сумму всех
XOR
-сумм для каждого подмножества
nums
.
Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз.
Массив
a
является подмножеством массива
b
, если
a
может быть получено из
b
путем удаления некоторых (возможно не удалением никаких) элементов
b
.
Входные данные
Программа получает на вход в первой строке натуральное число
n
- количество элементов массива
nums
. Во второй строке записаны
n
чисел
numsi
.
Ограничения
1 <= n <= 12
1 <= numsi <= 20
Выходные данные
Выведите ответ на задачу.
Пояснения к тестовым примерам
В первом примере
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6
Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
Примеры
№ | Входные данные | Выходные данные |
1
|
2
1 3
|
6
|
2
|
3
5 1 6
|
28
|