/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 行 N 列のマス目があり、上から i \, (1 \leq i \leq N) 行目、左から j \, (1 \leq j \leq N) 列目のマスを (i, j) と表します。
マス (i, j) には非負整数 a_{i, j} が書かれています。
マス (i, j) にいるとき、マス (i+1, j), (i, j+1) のいずれかに移動することができます。ただし、マス目の外に出るような移動はできません。
マス (1, 1) から移動を繰り返してマス (N, N) にたどり着く方法であって、通ったマス（マス (1, 1), (N, N) を含む）に書かれた整数の排他的論理和が 0 となるようなものの総数を求めてください。
排他的論理和とは
整数 a, b の排他的論理和 a \oplus b は、以下のように定義されます。- a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 20
- 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}
出力
答えを出力せよ。
入力例 1
3 1 5 2 7 0 5 4 2 3
出力例 1
2
次の二通りの方法が条件を満たします。
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)
入力例 2
2 1 2 2 1
出力例 2
0
入力例 3
10 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0
出力例 3
24307
Score : 500 points
Problem Statement
There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.
When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.
Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.
What is the exclusive logical sum?
The exclusive logical sum a \oplus b of two integers a and b is defined as follows.- The 2^k's place (k \geq 0) in the binary notation of a \oplus b is 1 if exactly one of the 2^k's places in the binary notation of a and b is 1; otherwise, it is 0.
In general, the exclusive logical sum of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). We can prove that it is independent of the order of p_1, \dots, p_k.
Constraints
- 2 \leq N \leq 20
- 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}
Output
Print the answer.
Sample Input 1
3 1 5 2 7 0 5 4 2 3
Sample Output 1
2
The following two ways satisfy the condition:
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).
Sample Input 2
2 1 2 2 1
Sample Output 2
0
Sample Input 3
10 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0
Sample Output 3
24307