Dinamik dasturlash
DP-04
DP-05
~/algor $ cat masalalar/xor-yollar
DP-05
XOR Yo'llar
Muallif:
Iqbolshoh Ilhomjonov
Qiyin
2000 ms
256 MB
95%
$N * M$ o'lchamli katakli panjara berilgan: $(i, j)$ katakda nomanfiy butun son $C_{i, j}$ yozilgan. Robot $(1, 1)$ katakdan $(N, M)$ katakka boradi va har qadamda faqat o'ngga — $(i, j + 1)$ ga yoki pastga — $(i + 1, j)$ ga o'tadi. Yo'l omadli hisoblanadi, agar yo'ldagi barcha kataklar (birinchi va oxirgisi ham) sonlarining bitli XOR ($\oplus$) natijasi $X$ ga teng bo'lsa. Nechta har xil omadli yo'l borligini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda uchta butun son: $N$, $M$ va $X$. Keyingi $N$ ta qatorning har birida $M$ tadan butun son $C_{i, j}$.
Chiquvchi ma'lumotlar
Bitta butun son — omadli yo'llar soni.
Izoh
$1 \le N, M \le 20$
$N + M \le 22$
$0 \le X \le 10^{9}$
$0 \le C_{i, j} \le 10^{9}$
Misollar
Kirish #1
3 3 11 2 1 5 7 10 0 12 6 4
Chiqish #1
3
Kirish #2
1 1 5 5
Chiqish #2
1