Модуль: meet in the middle


Задача

2 /5


Xor-пути в матрице

Задача

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 1018) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел ai,j, где j-й элемент i-й строки равен ai,j (0 <= ai,j <= 1018).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.
 
Примеры
Входные данные Выходные данные
1 3 3 11
2 1 5
7 10 0
12 6 4
3
2 3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
5



time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Комментарий учителя