LGV定理

· · 个人记录

LGV定理用于解决路径不相交问题。

定理

有 n 个起点 1, 2, 3, ..., n，它们 分别对应 要到 n 个终点 A, B, C, ..., X，并且要求路径点不相交。求方案数。

设 e_{i, W} 表示从起点 i 到终点 W 的方案数。则最终答案为：

e_{1, A} & e_{1,B} & ... & e_{1, X}\\ e_{2, A} & e_{2, B} & ... & e_{2, X}\\ ... & ... & ... & ...\\ e_{n, A} & e_{n, B} & ... & e_{n, X}\end{vmatrix}

（这俩竖线是行列式的意思）

其中 n = 2 的情况挺好理解的，因为它表示出来是:

e_{1, A} & e_{1, B}\\ e_{2, A} & e_{2, B}\end{vmatrix}

即：

e_{1, A} * e_{2, B} - e_{1, B} * e_{2, A}

前面部分是不考虑“不相交”的合法方案数。但是可能会有相交的情况。我们发现如果在第一个相交点的地方偷偷的交换一下路径的来源，那么每一种不合法路径唯一对应一种 1 到 B，2 到 A 的路径；同时每一种 1 到 B，2 到 A 的路径唯一对应一种不合法路径。因此可以用 e_{1, B} * e_{2, A} 来计算不合法路径。然后容斥即可。

这种方法类似求卡特兰数通项公式的方法。

实际上 n > 2 的情况也可以用容斥思想感性理解。

例题：CF348D Turtles