Вам задан целочисленный массив \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).
Определите количество подмассивов \(a\), у которых \(\operatorname{XOR}\) имеет четное количество делителей. Другими словами, определите количество пар индексов \((i, j)\) (\(i \le j\)) таких, что \(a_i \oplus a_{i + 1} \oplus \dots \oplus a_j\) имеет четное количество делителей.
Например, числа \(2\), \(3\), \(5\) или \(6\) имеют четное количество делителей, а \(1\) и \(4\) — нечетное. Считайте, что для данной задачи \(0\) имеет нечетное количество делителей.
Здесь \(\operatorname{XOR}\) (или \(\oplus\)) обозначает операцию побитового исключающего ИЛИ.
Выведите количество подмассивов, но умноженное на 2022... Так, давайте закончим. Просто выведите сам ответ.
Выходные данные
Для каждого набора входных данных выведите количество подмассивов, \(\operatorname{XOR}\) которых имеет четное количество делителей.
Примечание
В первом наборе входных данных есть \(4\) подмассива, \(\operatorname{XOR}\) которых имеет четное количество делителей: \([3]\), \([3,1]\), \([1,2]\), \([2]\).
Во втором наборе есть \(11\) подмассивов, \(\operatorname{XOR}\) которых имеет четное количество делителей: \([4,2]\), \([4,2,1]\), \([4,2,1,5]\), \([2]\), \([2,1]\), \([2,1,5]\), \([2,1,5,3]\), \([1,5,3]\), \([5]\), \([5,3]\), \([3]\).
В третьем наборе нет подмассивов, \(\operatorname{XOR}\) которых имеет четное количество делителей, так как \(\operatorname{XOR}\) любого подмассива равен либо \(4\), либо \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3
|
4
11
0
20
|