问题引入
问题来源：CF348D Turtles。
一个有障碍物的 $N\times M$ 网格图上，两只乌龟分别从 $(0,0)$ 点爬到 $(N-1,M-1)$ 点，询问路径不相交的方案数。
$N,M\leq 3000$ 。
首先问题可以转化为：两个人分别从 $A_0(0,1)$ 和 $B_0(1,0)$ 点出发，分别走到 $A_1(N-2,M-1)$ 和 $B_1(N-1,M-2)$ 的方案数。然后假设从点 $A$ 走到点 $B$ 的路径数为 $e(A,B)$ ，这个问题显然有一个 $O(NM)$ 的dp。
然后考虑如何去重，对于这个问题我们可以交换点 $A_0,B_0$ 的终点后再计算一次路径数，也就是说：从 $A_0$ 走到 $B_1$ ，$A_1$ 走到 $B_0$ 。本题的答案就是 $e(A_0,B_0)e(A_1,B_1)-e(A_0,B_1)e(A_1,B_0)$ 。
为什么成立？因为交换终点后，两条路径必定相交！于是，我们可以将这两条相交的路径想象成在最后一个交点处互换了身份，到达了对方的终点。
AC代码。
LGV引理
有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，若一个棋子在点 $(x,y)$，那么走一步只能走到 $(x+1,y)$ 或 $(x,y+1)$。
现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，最终要走到 $(b_i,n)$。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。
$n\leq 10^6,m\leq 100$ 。
先观察一下上面那题的结论：$e(A_0,B_0)e(A_1,B_1)-e(A_0,B_1)e(A_1,B_0)$ ，很容易联想到这是一个叉积：
e(A_0,B_0) & e(A_0,B_1) \\
e(A_1,B_0) & e(A_1,B_1) \\
\end{bmatrix}$$
因此，根据数学思想中的从特殊情况到一般情况，我们可以猜想这个行列式能否推广到 $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\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)$$
维基百科告诉我们这是对的，这个定理就是LGV引理。因此本题的答案就是这个行列式了，其中 $e(A_i,B_j)=\binom{n-1+b_j-a_i}{n-1}$ 。证明略，请参考维基百科中的证明。
简单地说，LGV引理用于求解不相交路径数问题时，就是上面那个矩阵的行列式，当满足一定限制条件时），这个行列式的值就是图上不相交路径的数量。具体而言，这个条件是：
- 有向无环图。
- 存在逆序对一定会导致路径相交。
从容斥原理的角度考虑这个行列式，实际上就是在做一个容斥系数为 $(-1)^{\sigma(S)}$（$\sigma(S)$ 表示逆序对数）的容斥，这个容斥成立的关键就在于存在逆序对一定会导致路径相交这一点上。这个容斥可以通过前文中交换终点的思想，脑补出来。因此，LGV引理可以在网格图上对于按照一定顺序排列的点集求不相交路径数量。
那么对于一般的DAG，LGV引理又能做什么呢？可以做一下 P7736 [NOI2021] 路径交点 ，其实根据行列式定义也比较容易想到，就是：交点个数为偶数的路径条数减去交点个数为奇数的路径条数。
练习题
在 $N\times M$ 的网格中填入 $[1,K]$ 中的数，要求左边的数小于等于右边的数，上面的数小于等于下面的数，求方案数。
根据单调性，这个矩形一定能用 $K-1$ 条分界线划分出来，每条分界线 $i$ 左上方的数 $\leq i$ ，右下方的数 $>i$ 。
由于每条分界线都是从 $(0,0)$ 出发，终点是 $(N,M)$ ，因此对第 $i$ 条分界线可以向右下移动 $i$ 个单位，那么所有的分界线一定就不相交了。因此本题转化为了起点集为 $(0,0),(1,-1),\ldots,(K-2,-(K-2))$ ，终点集为 $(N,M),(N+1,M-1),\ldots,(N+(K-2),M-(K-2))$ ，求不相交路径数。这就是个LGV引理的裸题。