Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

Задача D. Еще одна задача на XOR

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Вам дан массив $A$ из $n$ неотрицательных целых чисел, посчитайте количество пар чисел $1 \le l \le r \le n$, таких что $X \le A[l]\ xor\ A[l + 1]\ xor\ ...\ xor\ A[r]$, для некоторого заданного целого числа $X$. $xor$ — операция побитового сложения (в двоичной системе) по модулю два. Результатом этой операции является единица только в том случае, если биты операндов различны. Пример: $10_{10}\ xor\ 23_{10}\ =\ 29_{10}$, $1010_2\ xor\ 10111_2\ =\ 11101_2$, здесь записано одно и то же равенство в десятичной, а затем в двоичной системе счисления.

Формат входного файла

В первой строке входных данных содержится два целых числа, разделенных пробелом $n$ и $0 \le X \le 10^9$. В следующей строке заданы $n$ целых чисел разделенных пробелами. Каждое из этих чисел не превосходит $10^9$.

Формат выходного файла

Единственное число, ответ на задачу.

Примеры:

Вход

5 0
1 2 3 4 5

Ответ

15

Вход

3 3
1 2 3

Ответ

2

Замечание

Подзадача 1 — 31 баллов $1 \le n \le 1000$ Подзадача 2 — 69 балла $1 \le n \le 100000$

Комментарий/решение

Это задача решается с помощью цифрового бора