给定 n 维空间中的 2 个点 A=(a_1\dots a_n),B=(b_1\dots b_n)，从 A 开始走，每次将某一维坐标增加 1，同时要求经过的每个点 X 都满足 \forall i\in [1,n),x_i<x_{i+1}。问走到 B 的方案数。
本题也可以转化为给定形状的斜杨表填数方案计数，但这种方法扩展性不强，这里不再赘述。
先忽略对 X 的限制，那么答案显然为：
\dfrac{(\sum\limits_{i=1}^n (b_i-a_i))!}{\prod\limits_{i=1}^n (b_i-a_i)!}
我们考虑忽略 a_i 与 b_i 的对应关系，即对于 b 的 n! 种重排求出答案之和，显然如果 b 不是递增的那么答案一定为 0。这一部分是为了方便使用 LGV 引理。
对于一种不合法的方案，一定存在至少一对 (i,j) 在某个时刻 t 满足 x_i=x_j。我们找到所有这样的 (i,j) 中字典序最小的一组，在这个前提条件下要求 t 最大，并交换时刻 t 之后 i 和 j 这两维上的所有操作。设 B' 为 B 中交换 b_i 和 b_j 后得到的点，那么交换完之后所走到的终点会变为 B'。可以发现，这样构造出来的是一个不合法方案之间的双射。
根据这个双射，我们发现只需要求出：
\sum\limits_p(-1)^{inv(p)}\dfrac{(\sum\limits_{i=1}^n (b_{p_i}-a_i))!}{\prod\limits_{i=1}^n (b_{p_i}-a_i)!}
=(\sum\limits_{i=1}^n (b_{p_i}-a_i))!\sum\limits_p(-1)^{inv(p)}\dfrac{1}{\prod\limits_{i=1}^n (b_{p_i}-a_i)!}
=(\sum\limits_{i=1}^n (b_i-a_i))!\sum\limits_p(-1)^{inv(p)}\dfrac{1}{\prod\limits_{i=1}^n (b_{p_i}-a_i)!}
其中 p 是一个 1\sim n 的排列，inv(p) 是 p 的逆序对个数。
这是因为双射中每一组对应关系中的两种方案的 inv(p) 奇偶性一定不同，因此所有不合法方案对答案的贡献都是 0。而所有合法方案都有 inv(p)=0，所以上式即为合法方案数。
只需要构造一个 n\times n 的矩阵 M 满足对于任意一个 1\sim n 的排列 p 都满足：
\prod\limits_{i=1}^n M_{i,p_i}=\dfrac{1}{\prod\limits_{i=1}^n(b_{p_i}-a_i)!}
显然可以得到：
M_{i,j}=(b_j-a_i)!
答案即为：
(\sum\limits_{i=1}^n(b_i-a_i))!\det(M)
时间复杂度 O(n^3)。
本题的推理过程与 LGV 引理的证明方法几乎完全一致。从这题中我们也可以发现 LGV 引理不仅仅可以用于不相交路径计数，实际上只要能构造出不合法方案之间的双射就可以使用类似的方法。
给定一个 DAG，同时给定两个点的子集 S 和 T，问最多选出多少条不相交的路径满足每条路径起点在 S 中，终点在 T 中。
经典的做法是拆点跑最大流，但有些题目并不能用这种方法高效地解决。
我们随机选择一个大质数 p，对于图中的每条边随机赋一个 [1,p) 的权值。
定义一条路径的权值为这条路径中所有边的边权之积。
以 S 中的每个点为起点进行一次 dp 求出它到 T 中每个点的所有路径的权值之和。这一部分的时间复杂度为 O((n+m)|S|)。
这样我们得到了一个 |S|\times |T| 的矩阵。根据 LGV 引理，我们相当于要求出最大的 c 使得可以选择 c 行 c 列使得它们相交形成的 c\times c 矩阵的 c 长度为 c 行向量线性无关。
考虑固定选择的 c 行，如果可以选择 c 列使得满足条件，那么一定可以证明这 c 个长度为 |T| 的行向量线性无关。
因此答案即为原矩阵的 |S| 个长度为 |T| 的行向量的基的大小即可。
时间复杂度 O((n+m)|S|+|S|^2|T|)。可以证明这个随机化算法大概率正确。