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 <= 121 <= 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
|