介绍
Lindström-Gessel-Vienot Lemma可以用来解决一类路径计数问题。
要想将这个引理用于解决计数问题，首先需要令图的所有边的权值等于1。
接着需要说明的是，从起点 $$ A={a_{1},\ldots ,a_{n}} $$ 到终点 $$ B={b_{1},\ldots ,b_{n}} $$ 的所有不相交路径，并不是指$$ {a_{i} } $$一定到$$ {b_{i} } $$，它包括得更广，起点A中的某点到达终点B中的任意一点即可，但由于严格不相交，所以它们是一个“双射”。
公式的右边，计算的是所有路径的有符号权值和，这里的符号由排列的逆序对个数决定，假如逆序对的个数是奇数，那么符号为负，否则为正。
假如我们要求从起点 $$ A={a_{1},\ldots ,a_{n}} $$ 到终点 $$ B={b_{1},\ldots ,b_{n}} $$ ，且$$ {a_{i} } $$一定到$$ {b_{i} } $$的所有不相交路径，那么等式的右边就恰好等于这个方案数。
题目
题意
详情请看Monotonic Matrix。
分析
官方题解：
考虑 01 和 12 的分界线
是 (n, 0) 到 (0, m) 的两条不相交(可重合)路径
平移其中一条变成 (n-1, -1) 到 (-1, m-1)
变成起点 (n, 0) 和 (n-1, -1),终点 (0, m) 和 (-1, m-1) 的严格不相交路径
套 Lindström–Gessel–Viennot lemma
答案是 $$ {C_{n+m}^n}^2 - C_{n+m}^{m - 1} C_{n+m}^{n-1} $$
我们设左下角的两点为起点a1, a2，右上角的两点为终点b1, b2，我们需要求的是从a1到b1、a2到b2的路径方案数，由于题目的限制，a1到b2、a2到b1的路径是不合法的，所以，公式的右边恰好就不包含a1到b2、a2到b1的路径方案数了。因此，我们就可以通过计算矩阵行列式来计算答案了。
推广
留坑待填。