Problem
Viene specificato un campo rettangolare di dimensioni
n*m. Ogni cella contiene un numero intero non negativo. Devi contare il numero di percorsi dalla cella (1,1) alla cella (
n,
m) che soddisfano il seguenti condizioni.
1) Da ogni cella, puoi solo spostarti
giù o
destra senza lasciare il campo.
2) L'
OR esclusivo bit per bit di tutti i numeri sul percorso deve essere uguale a
k.
Trova il numero di percorsi corrispondenti per il campo specificato.
Inserimento
La prima riga contiene tre numeri interi
n,
m e
k (1 <= n, m <= 20, 0 <= k <= 10
18) - l'altezza e la larghezza del campo e il numero
k.
Le seguenti righe
n contengono ognuna
m interi
ai,j, dove
j -esimo elemento di
i-esima riga è uguale a
ai,j (0 <= a
i,j < ;= 1018).
Impressum
Stampa un numero intero: il numero di percorsi che soddisfano tutte le condizioni.
Esempi
| # |
Input |
Uscita |
| 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
3011
| 5 |