题解

思路推导

一条路径恰好经过 $n+m-1$ 个格子。直接枚举所有向右、向下的移动序列需要指数时间，但 $n,m\le20$，所以可以把路径从中间切开。

设总移动次数为 $L=n+m-2$，取前半段长度 $d=\lfloor L/2\rfloor$。从左上角走恰好 $d$ 步时一定落在同一条副对角线上。分别枚举从左上角走到这条副对角线的所有前缀，以及从右下角反向走到同一条副对角线的所有后缀。

做法

对每个中间格子，统计所有前缀路径的异或值及其出现次数。随后枚举到达该格子的每条后缀路径。前缀和后缀都包含中间格子，因此合并时中间格子的值被计算了两次，需要再异或一次消去重复。

若前缀异或值为 $x$、后缀异或值为 $y$、中间格子值为 $v$，整条路径的异或值为 $x\mathbin{\mathrm{xor}}y\mathbin{\mathrm{xor}}v$。因此后缀固定后，只需查询前缀中值为 $k\mathbin{\mathrm{xor}}y\mathbin{\mathrm{xor}}v$ 的路径条数并累加。

正确性证明

任意合法路径在走完前 $d$ 步后恰好到达一条固定副对角线上的唯一格子，因此它被唯一拆分为一条前缀路径和一条后缀路径。算法枚举了所有这样的前缀与后缀，所以不会遗漏任何路径。

对于同一中间格子的前后缀组合，二者的异或值都包含中间格子。再异或一次该格子的值后，中间格子只被保留一次，所得值正是整条路径上所有格子值的异或和。算法仅累加该值等于 $k$ 的组合，所以不会计入不合法路径。由拆分的唯一性，每条合法路径也只会被计数一次。

复杂度分析

两侧各枚举至多 $2^{\lceil (n+m-2)/2\rceil}$ 条半路径。时间复杂度为 $O(2^{(n+m)/2})$，空间复杂度为 $O(2^{(n+m)/2})$。