$dp$ 计数 + 容斥原理.
容易发现,每一行填的数都是从 $0\sim m$ 这 $m+1$ 个数中去掉一个数,将剩下的从小到大依次填进去形成的.
设 $f(i,j)$ 表示考虑了前 $i$ 行,第 $i$ 行去掉的数是 $j$ 的方案数.
为了满足第二个条件,观察可以得出 $f$ 的转移
$$
f(i,j)=\sum_{k=0}^{j+1} f(i-1,k)
$$
则答案为 $\sum_{j=0}^m f(n,m)= f(n+1,m-1)$ .
考虑将 $f(i,j)$ 与 $f(i,j-1)$ 做差,可以得出递推式
$$
f(i,j)=f(i,j-1)+f(i-1,j+1)
$$
直接 $dp$ 是 $O(n^2)$ 的,不能接受.
发现 $f$ 的转移形式与组合数比较像,尝试转化到坐标系中.
$f(n+1,m-1)$ 就表示从 $(0,0)$ 出发,每次可以向右走一步,或者向上与左走一步,走到 $(n+1,m-1)$ 方案数.
向上与左走的步数是确定的,要走 $n+1$ 步,那么向右走的步数就是 $n+m$ 步.
再转化一步,就变成从 $(0,0)$ 出发,只能向右走一步,或向上走一步,走到 $(n+1,n+m)$ 的方案数.
但现在向上走一步,对应的是原来向上,左各走一步,若原来的 $j<0$ 或者 $j>m$ 了,就不合法了.
也就是说,从 $(0,0)$ 走到 $(n+1,n+m)$ 时,还不能穿过直线 $y=x$ 和 $y=x-m$ .
记穿过 $y=x$ 再穿回来的事件为 $A$ ,穿过 $y=x-m$ 再穿回来的事件为 $B$ .
考虑容斥,考虑交错子序列 $ABABAB\dots$ ,则至少发生了前 $i$ 次事件的方案数 $s_i$ 对答案的贡献就是 $(-1)^i\cdot s_i$ .
将终点 $(n+1,n+m)$ 不断沿着两条直线对称,每对称一次就更新答案.
对另一个交错子序列 $BABABA\dots$ 也同样计算一遍贡献.
不断对称的时间复杂度是 $O(\log n)$ ,瓶颈在预处理阶乘及其逆元,时间复杂度 $O(n)$ .