考虑朴素的做法。共有 (n+m−2n−1)\dbinom{n+m-2}{n-1}(n−1n+m−2) 条可行路径,而此时程序用时显然超出限制。
容易想到使用双向搜索处理。将行与列从 111 开始进行编号。则可以以行号和列号之和为 ⌊n+m2⌋+1\left\lfloor\dfrac{n+m}2\right\rfloor+1⌊2n+m⌋+1 的格子作为分界线。第一次从左上角开始搜索,对于每个分界点,求出从左上角到达此格所有情况的路径异或和。第二次从右下角开始搜索,到达任意分界点时统计答案即可。
时间复杂度为 222 的指数级。
注册一个 HydroOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 HydroOJ 通用账户