考虑一个不太一样的双射。令 $inc_i,dec_i$ 分别为 $i$ 结尾的最长上升和下降子序列长度，那么我们维护两个 $N\times M$ 的矩阵 $A,B$，令 $A_{inc_i,dec_i}=i,B_{inc_i,dec_i}=p_i$。可以发现 $A$ 是行列单调增，$B$ 是行单调减列单调增，并且一对 $(A,B)$ 和 $p$ 是双射。

因此我们 DP 刻画出 $A$ 的形态，设 $f_s$ 表示填至形状为 $s$ 的方案数，其中 $s$ 是 $N \ge a_1 \ge a_2 \ge \dots \ge a_M \ge 0$ 的 $(a_1,a_2,\dots,a_M)$，共有 $\binom{N+M}N$ 种。则 $f(pos,val)$ 就是在 $A,B$ 的对应位置上分别是 $pos$ 和 $val$ 的 $(A,B)$ 对数。这可以用 $f$ 统计的结构拼出。

时间复杂度 $\Theta\left(\binom{N+M}N NM + (NM)^3\right)$。