LGV 引理（Lindstrom-Gessel-Viennot lemma）
王鲲鹏
·
·
题解
LGV 引理（Lindstrom-Gessel-Viennot lemma）
本文主要分为对 引理的阐述与证明 和 这道题的解法。然鹅OIer 不需要证明。
LGV 引理 内容
-
- 起点 A=\{a_1,\cdots,a_n\}，终点 B=\{b_1,\cdots,b_n\}。
- 每条边 e 有权 w_e，并假定值属于某 交换环 。
- 对于一个有向路径 P，定义 \omega(P) 为路径上所有边权的积。
- 对任意顶点 a，b，定义 e(a,b)=\sum\limits_{P:a \to b}{\omega(P)}。
设矩阵
M=
\begin{pmatrix}
e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\
e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\
\vdots & \vdots & \ddots & \vdots \\
e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \\
\end{pmatrix}
从 A 到 B 的不相交路径 P=(P_1,P_2,\cdots,P_n)，P_i 表示从 a_i 到 b_{\sigma(i)} 的一条路径，其中 \sigma 是一个排列（置换），并且满足对任意 i\not=j，P_i 与 P_j 没有公共点。记 \sigma(P) 表示 P 对应的排列。
引理说明，M 的行列式是所有从 A 到 B 的不相交路径 P=(P_1,\cdots,P_n) 的带符号和。其中符号指 \sigma(P) 的逆序数的奇偶性： (-1)^{\text{逆序数}}，记为 \mathrm{sign}(\sigma(P))。
\mathrm{det}(M)=\sum_{P:A\to B}{\mathrm{sign}(\sigma(P))\prod_{i=1}^{n}\omega(P_i)}
证明
对一组路径 P，若对任意 i\not=j，P_i 与 P_j 无公共点，则称 P 是一组不相交路径，否则为一组相交路径。为了简便，在下面相交路径记作 P^c，不相交路径记作 P^u。不做特殊说明时，P 为一组平凡的路径。当带下标时，指一条路径。定义 \omega(P)=\omega(P_1)\omega(P_2)\cdots\omega(P_n)。
根据定义，
\begin{aligned}
\mathrm{det}(M)
&=\sum_{\sigma \in S_n}\mathrm{sign}(\sigma)\prod_{i=1}^{n}e(a_i,b_{\sigma(i)}) \\
&=\sum_{\sigma \in S_n}\mathrm{sign}(\sigma)\prod_{i=1}^{n}\sum_{P_i:a_i \to b_{\sigma(i)}}\omega(P_i)
\end{aligned}
$$
\begin{aligned}
\mathrm{det}(M)
&=\sum_{\sigma \in S_n}\mathrm{sign}(\sigma)\sum_{P}\omega(P),P:(a_1,\cdots,a_n)\to(b_{\sigma(1)},\cdots,b_{\sigma(n)}) \\
&= \sum_{P:A \to B}\mathrm{sign}(\sigma(P))\omega(P)
\end{aligned}
$$
现在等式的形式已与定理相像，但是 $P$ 的含义不同。
$$
\mathrm{det}(M)=
\sum_{P^u:A \to B}\mathrm{sign}(\sigma(P^u))\omega(P^u)+\sum_{P^c:A \to B}\mathrm{sign}(\sigma(P^c))\omega(P^c)
$$
故若引理成立，必有 $\sum_{P^c:A \to B}\mathrm{sign}(\sigma(P^c))\omega(P^c)=0$ 。
设 $C$ 为所有 $P^c$ 构成的集合。如果我们能构造一个双射关系 $f:C \to C$，满足对任意 $P^c\in C$， $\omega(f(P^c))=\omega(P^c)$，$\mathrm{sign}(\sigma(f(P^c)))=-\mathrm{sign}(\sigma(P^c))$，根据重排列定理，
$$
\sum_{P^c}\mathrm{sign}(\sigma(P^c))\omega(P^c)
=\sum_{P^c}\mathrm{sign}(\sigma(f(P^c)))\omega(f(P^c))
$$
$$
\begin{aligned}
\sum_{P^c}\mathrm{sign}(\sigma(P^c))\omega(P^c)
&= \frac{1}{2}\sum_{P^c}\mathrm{sign}(\sigma(P^c))\omega(P^c)+\frac{1}{2}\sum_{P^c}\mathrm{sign}(\sigma(f(P^c)))\omega(f(P^c)) \\
&= \frac{1}{2}\sum_{P^c}\mathrm{sign}(\sigma(P^c))\omega(P^c)+\frac{1}{2}\sum_{P^c}-\mathrm{sign}(\sigma(P^c))\omega(P^c) \\
&= 0
\end{aligned}
$$
确实可以构造：
考虑 $P=(P_1,P_2,\cdots,P_n)$，$P \in C$，中找到最小的二元组 $(i,j)$ 满足 $P_i$ 和 $P_j$ 有交，将相交之后的路径交换一下，交换后得到 $P'$ 。显然有 $P' \in C$，$P' \not= P$。
这里就不写式子了 可以直观理解一下 ~~就是因为懒~~，因为边还是那些边，边权属于交换环，所以 $\omega(P)$ 不变。另一个影响是交换了两条路径的终止节点，即交换了排列中的两个元素，~~根据我们学前班就学过的线性代数~~，逆序对数的奇偶改变，所以 $\mathrm{sign}(\sigma(P'))=-\mathrm{sign}(\sigma(P))$。
最后我们还可以注意到，对于 $P'$，最小的二元组还应该是 $(i,j)$，那么 $f(P')=P$。籍此可证 $f$ 是双射。
证毕。
~~完结撒花lalala~~
~~差点忘了这道题还没有说...~~
#### [LuoguP6657](https://www.luogu.com.cn/problem/P6657) 模板
好像比定理削了好多东西...
因为这是在方格图上，因为坐标是单调的，当 $\sigma \not=(1,2,\cdots,n)$ 时，显然不存在不相交路径。
$$
\text{右式}=\sum_{P:(P_i:a_i\to b_i)}1
$$
即为所求。
那么构造矩阵，$e(a_i,b_j)=\binom{b_j-a_i+n-1}{n-1}$。高斯消元求行列式即可。
#### 参考资料
1. [维基百科](https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma) 挺详细的就是没中文...
2. [OI Wiki](https://oi-wiki.org/graph/lgv/).
真·完结撒花~~~
---
update 2021-05-27 感谢 @oisdoaiu 的指正