$$【组合数学】专题笔记目录$$

观察到矩阵的每一行都是单调递增的，并且每一行在 $[0,m]$ 仅有一个数没有出现。
设 $f_{i,j}$ 表示前 $i$ 行，第 $i$ 行没有的元素是 $j$ 的方案数。
至于转移，手模一下发现 $f_{i,j}=\sum_{k=0}^{j+1} f_{i-1,k} = \sum_{k=0}^j f_{i-1,k} + f_{i-1,j+1} = f_{i,j-1} + f_{i-1,j+1}$。
这个式子仍然是 $O(nm)$ 的，答案为 $f_{n+1,m}$，所以考虑优化。
现在画出转移图：搬图（来自洛谷）

这东西看着非常的难受，所以我们考虑把第 $i$ 行右移 $i-1$ 个位置。
由于平移之后仍然会有斜着的边，所以我们建立虚点，并让它先向上再向右转移。平移后的转移如图。

再画出两条绿色的直线，转移时不能碰到这两条线。

于是问题转化为：在坐标轴上从原点出发，只能向右向上走，求到达 $(n + m + 1, n)$，并且不能碰到直线 $a:y=x+1$ 和 $b:y=x-m-2$ 的路径方案数。

对于从 $(0,0)$ 出发到 $(x,y)$，如果没有直线的限制，显然方案数是 $\binom{x + y}{x}$。
这里有两条直线，考虑先后碰到 aabbabbbaa，由于连续碰触同一条直线对答案没有影响，所以可以收缩为 ababa。
我们发现它只会以 a 或以 b 开头，所以考虑分别计算答案，以 a 开头为例：
初中数学老师狂喜这是典型的将军饮马问题：

考虑把终点关于直线 a 翻折得到点 N，则任何经过 a 到达终点的路径都可以转化为从原点到点 N 的路径！所以用路径总数减去经过 a 的方案数就是答案了吗？
不，因为你只保证了不经过 a，它可能经过直线 b。那怎么办呢？
把 N 再关于直线 b 翻转，可以得出第一次不经过 a，第二次不经过 b 的方案数。那这是答案吗？
仍然不是，因为第三次还有可能经过 a。因此只能容斥，这样不断地加减贡献直到对称后的点在第二象限或第四象限，即无法到达。

现在考虑如何求出 $(a,b)$ 关于直线 $y=x+m$ 的对称点。
先把整个坐标系往下平移 $m$ 个单位，让直线变成 $y=x$，则 $(a,b)$ 转化为 $(a,b-m)$。
关于 $y=x$ 的对称点即横纵坐标交换，对称点坐标为 $(b-m,a)$。
最后再把对称点坐标往上移动 $m$ 个单位，得到原问题的解为 $(b-m,a+m)$。

以 b 开头的路径也是同理，就可以分类讨论并容斥解决这题了。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 15;
const int mod = 1e9 + 7;
int n, m;

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

int fac[N], inv[N];
void init() {
    fac[0] = 1;
    for (int i = 1; i <= 5000000; i++) fac[i] = (fac[i - 1] * 1ll * i) % mod;
    inv[5000000] = qmi(fac[5000000], mod - 2);
    for (int i = 4999999; i >= 0; i--) inv[i] = (inv[i + 1] * 1ll * (i + 1)) % mod;
}

int C(int n, int m) {
    return ((fac[n] * 1ll * inv[m]) % mod * 1ll * inv[n - m]) % mod;
}

int dp[N];

void get(int &a, int &b, int k) {  //(a,b) 关于 y=x+k 的对称点
    swap(a, b);
    a -= k, b += k;
}

long long ans = 0;

int main() {
    scanf("%d%d", &n, &m);
    init();
    int x = n + m + 1, y = n;
    ans = C(x + y, x);
    while (x >= 0 && y >= 0) {  //以a开头
        get(x, y, 1); ans = (ans - C(x + y, x) + mod) % mod;
        get(x, y, -m - 2); ans = (ans + C(x + y, x) + mod) % mod;
    }
    x = n + m + 1, y = n;
    while (x >= 0 && y >= 0) {
        get(x, y, -m - 2); ans = (ans - C(x + y, x) + mod) % mod;
        get(x, y, 1); ans = (ans + C(x + y, x) + mod) % mod;
    }
    printf("%d\n", ans);
    return 0;
}