Подсчитайте способы разбить массив на три непустых подмассива, имеющих одинаковые значения побитового исключающего ИЛИ.

Дан массив arr[] , состоящий из N неотрицательных целых чисел. Задача состоит в том, чтобы подсчитать количество способов разбить массив на три различных непустых подмассива, чтобы побитовое исключающее ИЛИ каждого подмассива было равно.

Примеры:

Input: arr[] = {7, 0, 5, 2, 7} 
Output: 2
Explanation: All possible ways are:
{{7}, {0, 5, 2}, {7}} where XOR value of each subarray is 7
{{7, 0}, {5, 2}, {7}} where XOR value of each subarray is 7

Input: arr[] = {3, 1, 4}
Output: 0

Наивный подход: самый простой подход — разбить массив на три непустых подмассива с помощью трех циклов и проверить, равны ли XOR каждого подмассива или нет. Если данное условие выполняется, то увеличьте окончательный счет. Распечатайте полученный окончательный счет.

Временная сложность: O(N ³ )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:

• Пусть xor_arr будет XOR всех элементов массива arr[] .
• Если arr[] можно разделить на три разных подмассива с одинаковыми значениями XOR, то XOR всех элементов в каждом подмассиве будет равен xor_arr .
• Итак, идея состоит в том, чтобы найти все массивы префиксов и суффиксов со значением XOR , равным xor_arr .
• Если общая длина такого массива префиксов и суффиксов меньше N, то между ними существует еще один подмассив со значением XOR, равным xor_arr .

Следовательно, подсчитайте общее количество всех таких массивов префиксов и суффиксов, которые удовлетворяют вышеуказанному условию. Выполните следующие шаги, чтобы решить данную проблему:

• Сохраните XOR всех элементов массива arr[] в переменной xor_arr .
• Создайте массив pref_ind[] для хранения конечных точек каждого массива префиксов, значение XOR которого равно xor_arr .
• Пройдите массив, arr[] и вставьте конечные точки каждого массива префиксов, значение XOR которого равно xor_arr в pref_ind .
• Создайте другой массив, suff_inds[] размера N , где suff_inds[i] хранит общее количество массивов суффиксов со значением XOR, равным xor_arr , начальная точка которого больше или равна i .
• Пройдите массив, arr[] в обратном порядке, чтобы заполнить массив suff_inds[] . Если текущее значение XOR массива суффиксов равно xor_arr , то увеличивается suff_inds[i] на 1 . Кроме того, добавьте значение suff_inds[i+1] к suff_inds[i] .
• Для каждого элемента idx в pref_ind , если значение idx < N-1 , добавьте значение suff_inds[idx + 2] к окончательному счету.
• Наконец, в качестве результата выведите значение окончательного счета.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)