格路径与计数

这属于组合数学里面的东西，单独拿出来谈上一谈。

最简单的计数：从 $(0, 0)$ 只能向右或者向左走到 $(n, m)$。

首先有一个很 naive 的 DP：$f_{i, j} = f_{i - 1,j} + f_{i, j - 1}$。

然而如果我们稍微变换一下坐标，旋转 45 度，那么递推式变为：$g_{k, j} = g_{k - 1, j} + g_{k - 1, j - 1}$，这与 $n \choose i$ 何其相似，所以可以得到 $g_{k, j} = {k \choose j}$，也就是说 $f_{i, j} = g_{i + j, i} = {i + j \choose j}$。

是否能够换一个通用的方式理解？

要走到 $n + m$，那么一共需要走 $n + m$ 步，而其中横走 $n$ 步，在其中选择 $n$ 个位置横着走，那么方案数就是 ${n + m \choose n}$。

那么现在，如果我们可以斜着走，也就是走到 $(i + 1, j + 1)$，那么路径数如何？

还是考虑最基本的 DP，$f_{i, j} = f_{i - 1, j} + f_{i, j - 1} + f_{i - 1, j - 1}$，这下变换坐标观察就啥也观察不出来。

不妨考虑枚举斜着走的步数，如果走了 $x$ 步，那么横着和竖着走的步数就分别变为了 $n - x, m - x$，这又归约为了上一个问题，但是什么时候斜着走？发现只需要在原本的行走路径上随便插入 $x$ 步斜着的都是合法的。

于是最终的路径数为 $\sum_{d = 0}^{\min(n, m)} \binom{n + m - 2d}{n - d} \binom{n + m - d}{d}$。

这还不够，在学习卡特兰数的时候，其与格路径的关系非常密切：不超过对角线到 $(n, n)$ 的路径数。

如果简单推广一下，不超过对角线到 $(n, m)$ 该如何计数？（这里不妨设 $n \ge m$）

考虑简单容斥，一共有 $n + m \choose n$ 条路径，而不合法的？

我们将不超过 $y = x$ 这条线的限制改为不经过 $y = x + 1$ 这条线。

对于每一条经过了 $y = x + 1$ 的路径，我们将第一次经过前的部分关于 $y = x + 1$ 对称一下，那么起点就变为了 $(-1, 1)$。不难发现，$(-1, 1) \to (n, m)$ 的路径与不合法的路径一一对应，所以不合法的路径数为 $n + m \choose n + 1$，最终的答案即是 $\binom {n + m} n - \binom{n + m}{n + 1}$，这是符合卡特兰数的。

这种翻折的思路正是大名鼎鼎的折线法，之后还会提及。

继续加强，可以走斜对角线呢？那么发现斜对角线不会影响路径的合法性，所以枚举斜着走的步数，剩下的就和前面一样了。

然而我们不会满足于不超过 $y = x$ 这条简单的线的限制，如果是不超过 $y = x + k$ 该何去何从？

还是折线法，但是对称的线变了，变成了 $y = x + k + 1$ （注意特判一下本就一定超过的情况）

继续，如果考虑上不过 $y = x + a$，下不过 $y = x + b$ 又该如何？

现在就是大名鼎鼎的折线容斥（呃，反射容斥）了

如果简单的利用上面的做法，那么会发现我们重复计算了同时经过 $a, b$ 的情况，所以要减去，但是会发现会多减去经过 $aba$ 或者 $bab$ 的线段，又要加上……

如此往复，直到对称着对称着没有值了，那么就胜利了（这是一定可以越界的！）

形式化来说，设序列 $xyxyx...$ 表示经过两者的顺序，那么方案数为 $\binom{n + m}{n} + \sum_{len = 1} (-1)^{len} abab... + \sum_{len = 1} (-1)^{len} baba...$

其中 $len$ 表示 $abab...$ 序列的长度。而直接求这个是 $O(\log n)$ 的，非常的优秀。

重新回到格路径，这样子分析怪简单的，能不能再抽象一点？

显然是可以的，这就上升到生成函数了，这就确实抽象了。