卡特兰数与反射容斥

不知所云。

---

卡特兰数

卡特兰数是一种 OI 中可能常用的序列，序列前几项为：\(1, 2,5,14,42,132,429,1430,4862\)，我们记作 \(H_i\)。

卡特兰数有以下应用：

• 求长度为 \(n\) 的合法出栈序列。
• 求长度为 \(2n\) 的合法括号序列。
• 求从 \((0,0)\) 到 \((n,n)\)，其中不跨过 \(y = x\) 这条直线的方案数。
• ……

仔细思考后就会发现上述三种问题本质上都是同一类，都可以抽象成第三个问题来解决。

我们先研究最后一个问题，我们先写出来一个递推形式的计算方法。

我们枚举第一个与 \(y = x\) 交上的点，就有：

\[H_n = \sum_{i = 1}^{n} H_{i - 1} H_{n - i} = \sum_{i = 0}^{n - 1} H_i H_{n - i - 1} \]

证明可以考虑从 \((0,0)\) 走到 \((i, i)\) 且不经过 \(x = y\) 的方案数为 \(H_{i - 1}\)，从 \((i, i)\) 走到 \((n, n)\) 且不跨过 \(y = x\) 的方案数为 \(H_{n - i}\)，注意此处用词不同。

接下来我们考虑如何写出来一个 \(O(1)\) 的式子，接下来就是玄学：

我们将第一次到达 \(y = x + 1\) 的路径上的点之后的路径沿 \(y = x + 1\) 对称过去，这样就会到达 \((n - 1, n + 1)\) 可以证明能够到达 \((n - 1, n + 1)\) 的路径与非法到达 \((n, n)\) 的路径一一对应，然后我们就得到了：

\[H_n = C_{2n}^{n} - C_{2n}^{n - 1} \]

反射容斥

网格上只有一条线不能经过的已经解决了，接下来我们解决有两条线不能经过的，我们记录这两条直线为 \(A, B\)。那么我们可以把与一条线一直相交的方案只记录第一次。我们把 \(f(ABA)\) 记作先与 \(A\) 相交，接着与 \(B\) 相交，最后与 \(A\) 再相交一次后到达 \((n, n)\) 的方案数。

那么根据容斥原理，答案就为：

\[f(\phi) - f(A) - f(B) + f(AB) + f(BA) - f(ABA) - f(BAB) + ... \]

接下来我们考虑如何计算 \(f\) 函数。

首先 \(f(A)\) 是将 \((n, n)\) 关于 \(A\) 对称后任走到达那个点的方案数，\(f(B)\) 是将 \((n, n)\) 关于 \(B\) 对称后任走到达那个点的方案数，这两个在上面就已经讨论过了。

之后我们考虑先解决 \(f(AB)\) 之后直接就能类比出 \(f\) 函数如何解决。

我们将 \((n,n)\) 关于 \(B\) 对称，这样可以求出来 \(f(B)\)，然后把这个对称后的点在关于 \(A\) 对称，这样可以就可以任走求出 \(f(AB)\)。

之后我们就解决了这个问题，来看一下题。

「JLOI2015」骗我呢

这个大力 \(O(nm)\) dp 是好做的，我们考虑设以下状态：\(dp_{i,j}\) 表示前 \(i\) 行，\(j\) 没出现的方案数，就有：

\[dp_{i, j} = \sum_{k = 0}^{j + 1} dp_{i - 1, k} \]

我们画个转移的图：

你就会发现这样还是太复杂了，考虑如何简化：

但是这个斜线看着让人难受，于是我们给他拉直：

注意：此处的灰色点是我们建出的虚点，仅仅是辅助转移用，之后我们给他套到坐标系里：

你就发现问题就变为了到达 \((n + m + 1, n)\) 且不经过 \(y = x + 1\) 与 \(y = x - (m + 2)\) 的方案数，反射容斥以下就做完了。