好像是常规做法，所以其实是 ARC146F。

Qiuly · 2023-03-22 16:14:21 · 题解

注意我们只关心点的相对位置，并且只关心匹配，也不关心每轮选了什么点。先求出总方案数（即 2n 个点配对的方案数，可以简单 DP），然后考虑接下来怎么做。

直接在网格图上走就是不能碰到上下边界，但是每次往下走时会计算贡献，不好处理。注意到只需要考虑每个左侧匹配点可能匹配的右侧匹配点数。记这个序列为 a_{1,n}，倒着考虑，不难发现限制有 1\leq a_{i}\leq k,a_n=1 以及 a_i\leq a_{i+1}+1 。而系数是 \prod a（从可选右端点选一个）。

重新放回网格发现形式和 ARC146F 是一致的。于是只要计算出带容斥系数的极长下降段的系数和，然后拼接答案即可。前者分治将矩阵乘起来就行，后者是求逆。

提交记录：Submission #39943355 - AtCoder Regular Contest 137 。