102715: [AtCoder]ABC271 F - XOR on Grid Path
Description
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
Input
题意翻译
给定一个n行n列的矩阵，定义合法路径为只向右或向下的路径，且途径数字异或和为0。求合法路径条数。Output
分数：$500$ 分
问题描述
有一个 $N$ 行 $N$ 列的网格。我们用 $(i, j)$ 表示从上数第 $i$ 行 $(1 \leq i \leq N)$、从左数第 $j$ 列 $(1 \leq j \leq N)$ 的方格。
方格 $(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)$ 为 $1$ 当且仅当 $a$ 和 $b$ 的二进制表示中第 $2^k$ 位恰有一个为 $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