Lindström–Gessel–Viennot Lemma
Lindström–Gessel–Viennot Lemma
作为一个特殊情况，引理提供对给定一个起点终点对集（记起点集为 $A$ 终点集为 $B$ ，且路径为 $ a_i \to b_i $ ），统计不相交路径数。
引理的内容如下：
令 $ \omega(P) := $ 路径 $ P $ 的边权积， $ e(a,b) := \sum_{P:a\to b} \omega(P) $ ，
$$ M := \left( \begin{matrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_m) \\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_m) \\ \vdots & \vdots& \ddots & \vdots \\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_m) \end{matrix} \right) $$
该引理宣称，$ \det|M| $ 给出$ A $ 到 $ B $ 不相交路径的权值和。
特殊情况，令各边边权为$1$，此时$|M|$为不相交路径数。
更一般情况，$ \omega $ 可以是形式变量，则 $e$ 将成为形式幂级数。
假定我们在网格图中，从第 $1$ 行的起点走到第 $n$ 的终点。
首先假设我们只有两对点 $ (a_1,b_1),(a_2, b_2) $ ，不考虑相交，则总路径数为 $ {b_1-a_1+n-1\choose n-1}{b_2-a_2+n-1 \choose n-1} $ .
考虑 $ a_1\to b_1, a_2 \to b_2 $ 相交，则在最后一个相交点之后交换路径，则得到 $ a_1\to b_2,a_2 \to b_1 $ 的路径。
考虑 $ a_1 \to b_2, a_2 \to b_1 $ 的路径，其必相交，则在最后一个相交点之后交换路径。
此时我们建立了 $ a_1 \to b_1, a_2 \to b_2 $ 的相交路径与 $ a_1 \to b_2, a_2 \to b_1 $ 的一一对应。
所以除去不合法情况后，答案为 $ {b_1-a_1+n-1\choose n-1}{b_2-a_2+n-1 \choose n-1} - {b_1-a_2+n-1\choose n-1}{b_2-a_1+n-1 \choose n-1} $ .
接着考虑多组路径，使用容斥原理。
假设某些路径相交，则在最后一个相交点之后交换路径，得到 $ B $ 的重排 $ C $ .
所以我们只需考虑 $ C $ 的逆序对数，为奇数则贡献为负，否则为正。
展开写，总的式子即为
$$ \sum _{C \subset B\text{的重排}} (-1)^{\tau(C)} \prod_{i=1}^n {c_i-a_i+n-1\choose n-1}. $$
注意到这就是一个行列式。
把对应的组合数换为路径数的记号的话，就是引理的内容了，证明同理。
在学习 Matrix Tree 定理的时候看到这个东西。觉得很妙。
思考理解方式跟之很像。
Codeforces 348D
在有障碍网格图中，统计多少从 $(1,1)$ 到 $(n,m)$ 的不交路径对。
Sol.
对 $ A = \{(1,2),(2,1)\}, B = \{(n-1,m),(n,m-1)\} $ 使用 LGV 引理即可。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 3e3 + 100, mod = 1e9 + 7;
char s[maxn][maxn];
long long dp[maxn][maxn];
int main()
{
int n, m; read(n, m);
for(int i = 0; i < n; ++i) scanf("%s", &s[i]);
if(s[0][1] != '#') dp[0][1] = 1;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(s[i][j] != '#')
{
if(i > 0) (dp[i][j] += dp[i - 1][j]) %= mod;
if(j > 0) (dp[i][j] += dp[i][j - 1]) %= mod;
}
long long a = dp[n - 2][m - 1], b = dp[n - 1][m - 2];
memset(dp, 0, sizeof dp);
if(s[1][0] != '#') dp[1][0] = 1;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(s[i][j] != '#')
{
if(i > 0) (dp[i][j] += dp[i - 1][j]) %= mod;
if(j > 0) (dp[i][j] += dp[i][j - 1]) %= mod;
}
long long c = dp[n - 2][m - 1], d = dp[n - 1][m - 2];
printf("%d\n", (a * d % mod - b * c % mod + mod) % mod);
return 0;
}
HDU 5852
给网格图。只能向下和向右走。给出第一行和第 $ n $ 行的 $ k $ 组对应的起点和终点，保证对应递增。问不相交路径方案数。
Sol.
直接用 LGV 就好了。
用组合数来算路径，以及 Gaussian Elimination 的时候要注意是在模意义下，别傻傻用浮点数。
Code (296ms, 4944kB)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 100 + 100, mod = 1e9 + 7, maxm = 2e5 + 10;
long long a[maxn][maxn];
long long fac[maxm], inv[maxm];
inline long long power(long long a, long long b)
{
long long ret = 1;
for(; b; b >>= 1, (a *= a) %= mod) if(b & 1)
(ret *= a) %= mod;
return ret;
}
inline long long C(long long a, long long b){return fac[a] * inv[b] % mod * inv[a - b] % mod;}
int k;
long long det()
{
long long ret = 1, sgn = 0;
for(int i = 0; i < k; ++i)
{
int t = i;
for(; a[t][i] == 0; ++t);
if(t >= k) return 0;
for(int j = i; j < k; ++j) swap(a[i][j], a[t][j]);
sgn *= -1;
long long inv = power(a[i][i], mod - 2);
for(int j = i + 1; j < k; ++j) if(a[j][i] != 0)
{
long long c = a[j][i] * inv % mod;
for(int l = i; l < k; ++l) ((a[j][l] -= c * a[i][l] % mod) += mod) %= mod;
}
(ret *= a[i][i]) %= mod;
}
return (ret + mod) % mod;
}
int s[maxn], t[maxn];
int main()
{
int t; read(t);
fac[0] = 1; for(int i = 1; i < maxm; ++i) fac[i] = fac[i - 1] * i % mod;
inv[maxm - 1] = power(fac[maxm - 1], mod - 2);
for(int i = maxm - 2; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
while(t--)
{
memset(a, 0, sizeof a);
int n; read(n, k);
for(int i = 0; i < k; ++i) read(s[i]);
for(int j = 0; j < k; ++j) read(::t[j]);
for(int i = 0; i < k; ++i) for(int j = 0; j < k; ++j) if(s[i] <= ::t[j])
a[i][j] = C(::t[j] - s[i] + n - 1, n - 1);
printf("%I64d\n", det());
}
return 0;
}