基本定义
LGV 引理可以用来处理有向无环图不相交路径对计数等问题。注意是有向无环图。
\(\omega(p)\) 表示路径 \(p\) 上边权之积。处理路径计数问题时大可将边权设做 \(1\)。
\(\{a\to b\}\) 表示 \(a\) 点到 \(b\) 点的所有路径的集合。
\(e(a,b)=\sum_{p\in\{a\to b\}}\omega(p)\)。处理路径计数问题时就是路径方案数。
起点集合 \(S\) 与终点集合 \(T\)，为图上大小相等（令其大小作 \(n\)）的两个点集。
定义一组 \(A\to B\) 的路径组 \(P\) 为满足下述条件的 \(n\) 条路径的集合：\(P_i\in\{A_i\to B_{\pi(P)_i}\}\)，且 \(\forall i\ne j\)。\(\pi(P)\) 是一个 \(1\) 到 \(n\) 的排列。定义一个路径组为不相交路径组当且仅当 \(\forall i\ne j\)，满足 \(P_i\) 与 \(P_j\) 无公共顶点。
令 \(\phi(\pi)\) 为满足 \(\forall i\in[1,n]\cap Z,P_i\in\{A_i\to B_{\pi_i}\}\) 的路径组 \(P\) 的集合。
\(\{A\Rightarrow B\}\) 表示 \(A\to B\) 的所有路径组的集合。\(\{A\Rightarrow_d B\}\) 表示 \(A\to B\) 的所有不相交路径组的集合。\(\{A\Rightarrow_i B\}=\{A\Rightarrow B\}\setminus\{A\Rightarrow_d B\}\)。
\(\tau(\pi)\) 表示排列 \(\pi\) 的逆序数。
LGV 引理
构造矩阵 \(M\) 满足 \(M_{i,j}=e(S_i,T_j)\)，则：
证明
故而我们只需证明：
对于一组相交路径组 \(P\)，我们找到任意一个交点对应的两条路径（多条路径交于一点任选两条），互换这两条路径的终点及这个交点到各自终点这一段路径，其余部分和路径保持不变，会得到另一个相交路径组，并且二者 \(\tau\) 奇偶性不同。显然我们可以用上述方式将所有相交路径组两两配对，得证。
特殊形式
如果存在唯一一个 \(\pi\) 满足 \(\phi(\pi)\cap \{S\Rightarrow_d T\}\ne\varnothing\)，那么构造矩阵 \(M\) 满足 \(M_{i,j}=e(S_i,T_{\pi_j})\)（这里 \(e\) 仅表路径数），则 \(\det(M)\) 即为 \(S\to T\) 的不相交路径组组数。
例题
CF348D Turtles
就是板子，不难发现第一步必须一个往上一个往右，最后一步也是，故而有两个起点和终点，并且不难发现满足特殊形式性质，直接 LGV 引理处理即可。
code
const int N=3005;int n,m;
char g[N][N];
mint f[N][N][2];inline mint det(vec<vec<mint>> v){int n=v.size();mint res=1;repl(i,0,n)repl(j,i+1,n)if(v[j][i].x){if(!v[i][i].x)swap(v[i],v[j]),res*=-1;else{mint d=v[j][i]/v[i][i];repl(k,0,n)v[j][k]-=d*v[i][k];}}repl(i,0,n)res*=v[i][i];return res;
}inline void Main(){cin>>n>>m;rep(i,1,n)rep(j,1,m)cin>>g[i][j];if(g[1][2]=='#'||g[2][1]=='#'||g[n-1][m]=='#'||g[n][m-1]=='#')return put(0),void();f[n-1][m][0]=f[n][m-1][1]=1;per(i,n,1)per(j,m-max(0,i-n+2),1)if(g[i][j]=='.')rep(k,0,1)f[i][j][k]=f[i+1][j][k]+f[i][j+1][k];vec<vec<mint>> v;v.resize(2,vec<mint>(2));rep(i,0,1)rep(j,0,1)v[i][j]=(i?f[2][1]:f[1][2])[j];put(det(v));
}