LGV 引理
算法简介
一种统计有向无环图不相交路径集的算法。
算法原理
定义路径的权值 $w(P)$ 表示路径 $P$ 的所有边权之积。
定义 $e(u,v)$ 表示所有 $u\to v$ 的路径的权值之和，即 $e(u,v)=\sum_{P\in\{u\to v\}}w(P)$。
定义起点集合为 $A$，其中第 $i$ 个起点为 $a_i$。终点集合为 $B$，其中第 $i$ 个终点为 $b_i$。
定义路径组的集合 $S(A,B)$，$S(A,B)$ 中的每个元素 $c$ 表示一个路径组，含有 $n$ 条路径，其中第 $i$ 条路径 $a_i\to b_{p_i}$，$P$ 是 $1\sim n$ 的排列。
定义 $N(c)$ 表示路径组 $c$ 的 $P$ 排列中的逆序对个数，$w(c)$ 表示路径组 $c$ 的所有路径权值之积。
设
$$ M=\begin{bmatrix} 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{bmatrix} $$
则有
$$ \det M=\sum_{c\in S(a,b)}(-1)^{N(c)}w(c) $$
特别的，令图上所有边权为 $1$，同时限定 $a_i$ 的对应点一定是 $b_i$，即 $c$ 的排列就是 $1\sim n$。
此时有 $N(c)=0,w(c)=1$，于是
$$ \det M=\sum_{c\in S(a,b)}1 $$
算法模板
给定一个二维平面，求满足如下条件的 $k$ 元路径组个数：
- 第 $i$ 条路径 $(1,a_i)\to (n,b_i)$
- 每次移动只能选择 $(x,y)\to (x,y+1),(x+1,y)$
显然 $e(i,j)={n-1+b_j-a_i\choose n-1}$，然后直接跑高斯消元板子。
