格路径与计数

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

最简单的计数：从 \((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)\) 的，非常的优秀。

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

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