题解

思路

两只乌龟在第一步必须分别走到 $(1,2)$ 和 $(2,1)$，在最后一步前必须分别位于 $(n-1,m)$ 和 $(n,m-1)$。单调性保证上方路径和下方路径的次序不会交换。

做法

子任务 1 枚举所有起点到终点的单调路径，记录内部格子集合，再枚举两条路径检查交集。

子任务 2 按斜线同步推进两只乌龟，状态记录它们当前的两个行号。只保留上方乌龟行号严格小于下方乌龟行号的状态，复杂度为 $O((n+m)n^2)$。

满分使用 Lindström–Gessel–Viennot 引理。记 $P(S,T)$ 为从 $S$ 到 $T$ 的单调可行路径数，则两条内部不相交路径的数量为

$$P((1,2),(n-1,m))P((2,1),(n,m-1)) -P((1,2),(n,m-1))P((2,1),(n-1,m)).$$

四个 $P$ 均用普通网格 DP 求出。

复杂度

满分算法的时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。