English · Original
Chinese · Translation
Formal · Original
There is a rectangular grid of size $n \times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left cell ($1, 1$) to the bottom-right cell ($n, m$) meeting the following constraints:
* You can move to the right or to the bottom only. Formally, from the cell ($i, j$) you may move to the cell ($i, j + 1$) or to the cell ($i + 1, j$). The target cell can't be outside of the grid.
* The _xor_ of all the numbers on the path from the cell ($1, 1$) to the cell ($n, m$) must be equal to $k$ (_xor_ operation is the bitwise exclusive OR, it is represented as '_^_' in Java or C++ and "_xor_" in Pascal).
Find the number of such paths in the given grid.
## Input
The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 20$, $0 \le k \le 10^{18}$) — the height and the width of the grid, and the number $k$.
The next $n$ lines contain $m$ integers each, the $j$\-th element in the $i$\-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 10^{18}$).
## Output
Print one integer — the number of paths from ($1, 1$) to ($n, m$) with _xor_ sum equal to $k$.
[samples]
## Note
All the paths from the first example:
* $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$;
* $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$;
* $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$.
All the paths from the second example:
* $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;
* $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;
* $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$;
* $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$;
* $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$.
有一个大小为 $n \times m$ 的矩形网格。每个格子上写有一个数字，格子 $(i, j)$ 上的数字为 $a_{(i, j)}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数量，满足以下条件：
求出满足上述条件的路径数量。
输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 20$，$0 \leq k \leq 10^{18}$），分别表示网格的高度、宽度和数字 $k$。
接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{(i, j)}$（$0 \leq a_{(i, j)} \leq 10^{18}$）。
请输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的路径中，异或和等于 $k$ 的路径数量。
第一个示例中的所有路径：
第二个示例中的所有路径：
## Input
输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 20$，$0 \leq k \leq 10^{18}$），分别表示网格的高度、宽度和数字 $k$。接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{(i, j)}$（$0 \leq a_{(i, j)} \leq 10^{18}$）。
## Output
请输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的路径中，异或和等于 $k$ 的路径数量。
[samples]
## Note
第一个示例中的所有路径：
$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3)$；
$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (3, 3)$；
$(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3)$。
第二个示例中的所有路径：
$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4)$；
$(1, 1) \to (2, 1) \to (2, 2) \to (3, 2) \to (3, 3) \to (3, 4)$；
$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (2, 4) \to (3, 4)$；
$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to (3, 4)$；
$(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3) \to (3, 4)$。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the grid.
Let $ k \in \mathbb{Z}_{\geq 0} $ be the target XOR value.
Let $ A = (a_{i,j}) \in \mathbb{Z}_{\geq 0}^{n \times m} $ be the grid, where $ a_{i,j} $ is the value in cell $ (i,j) $.
A *path* is a sequence of cells $ (i_1, j_1), (i_2, j_2), \dots, (i_\ell, j_\ell) $ such that:
- $ (i_1, j_1) = (1,1) $,
- $ (i_\ell, j_\ell) = (n,m) $,
- For all $ t \in \{1, \dots, \ell-1\} $, $ (i_{t+1}, j_{t+1}) $ is either $ (i_t + 1, j_t) $ or $ (i_t, j_t + 1) $.
The *XOR sum* of a path is the bitwise XOR of all $ a_{i_t,j_t} $ along the path:
$$
\bigoplus_{t=1}^{\ell} a_{i_t, j_t}
$$
**Constraints**
1. $ 1 \leq n, m \leq 20 $
2. $ 0 \leq k \leq 10^{18} $
3. $ 0 \leq a_{i,j} \leq 10^{18} $ for all $ i \in \{1,\dots,n\}, j \in \{1,\dots,m\} $
**Objective**
Compute the number of paths from $ (1,1) $ to $ (n,m) $ such that the XOR sum of the values along the path equals $ k $.
API Response (JSON)
{
"problem": {
"name": "F. Xor-Paths",
"description": {
"content": "There is a rectangular grid of size $n \\times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1006F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is a rectangular grid of size $n \\times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有一个大小为 $n \\times m$ 的矩形网格。每个格子上写有一个数字，格子 $(i, j)$ 上的数字为 $a_{(i, j)}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数量，满足以下条件：\n\n求出满足上述条件的路径数量。\n\n输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \\leq n, m \\leq 20$，$0 \\leq k \\l...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid. \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the target XOR value. \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}_{\\geq 0}^{n \\times ...",
"is_translate": false,
"language": "Formal"
}
]
}