首先仍然先模拟操作，记 $c_i$ 为 $(i,j)$ 对数，满足 $i>j$ 且 $(i,j)$ 可以匹配，下文称这样的 $j$ 为 $i$ 的后继。

然后考虑倒着扫所有点，记 $f_{i,j}$ 为扫了 $i\sim n$ 匹配了 $j$ 对的方案数。

考虑从 $f_{i+1}\to f_i$。

1. 如果 $i$ 搁置到一边，那么 $f_{i+1,j}\to f_{i,j}$；
2. 如果 $i$ 没动过，那么考虑对于一组匹配 $(u,v)$ 满足 $i>u>v$，那么 $(u,v)$ 无论如何都无法蠕动到 $i$ 前面，所以 $i$ 的后继必然有 $u,v$，并且所有可能的匹配都在 $i$ 的后继中选，所以 $i$ 还有 $c_i-2j$ 种匹配方法，那么 $f_{i+1,j}\times(c_i-2j)\to f_{i,j+1}$；
3. 如果 $i$ 被移动过，说明一定有后面的点要冲到 $i$ 前面，仍然考虑对于一组匹配 $(u,v)$ 满足 $i>u>v$，仍然由于 $(u,v)$ 无论如何都无法蠕动到 $i$ 前面，那么这样的匹配由于 $i$ 动过故不可能为 $i$ 的后继之一，所以 $i$ 有 $c_i$ 种匹配方法，那么 $f_{i+1,j}\times c_i\to f_{i,j+1}$。

复杂度 $O(nm+n^2)$。