文章目录
引入
简介
定义
引理
证明
例题
释疑
扩展
引入
有这样一个问题：
甲和乙在一张网格图上，初始位置
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
(x_1,y_1),(x_2,y_2)
(x1,y1),(x2,y2) ，分别要走到
(
x
3
,
y
3
)
,
(
x
4
,
y
4
)
(x_3,y_3),(x_4,y_4)
这个问题我们可以用稍微复杂的容斥做，也可以用类似卡塔兰数两个组合数相减公式的推导方法，我们会发现
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1) 到
(
x
4
,
y
4
)
(x_4,y_4)
(x4,y4) 的路径数乘上
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2) 到
(
x
3
,
y
3
)
(x_3,y_3)
(x3,y3) 的路径数刚好就是路径相交，也就是不合法的方案数，因为这两条路径一定交叉了嘛，所以等价于在第一个交叉位置上甲乙身份互换了，然后跑到对方终点的方案，这和相交的方案数是相等的。
因此答案就为
c
n
t
(
x
1
,
y
1
)
→
(
x
3
,
y
3
)
∗
c
n
t
(
x
2
,
y
2
)
→
(
x
4
,
y
4
)
−
c
n
t
(
x
1
,
y
1
)
→
(
x
4
,
y
4
)
∗
c
n
t
(
x
2
,
y
2
)
→
(
x
3
,
y
3
)
cnt_{(x_1,y_1)\rightarrow(x_3,y_3)}*cnt_{(x_2,y_2)\rightarrow(x_4,y_4)}-cnt_{(x_1,y_1)\rightarrow(x_4,y_4)}*cnt_{(x_2,y_2)\rightarrow(x_3,y_3)}
cnt(x1,y1)→(x3,y3)∗cnt(x2,y2)→(x4,y4)−cnt(x1,y1)→(x4,y4)∗cnt(x2,y2)→(x3,y3)
那么如果甲乙丙丁戊己庚辛壬癸……多达上百人要分别从一个位置到另一个位置，要求路径都不相交呢？
那就只能用
L
G
V
\rm LGV
LGV 引理 了。
简介
L
i
n
d
s
t
r
o
¨
m
–
G
e
s
s
e
l
–
V
i
e
n
n
o
t
l
e
m
m
a
\rm Lindström–Gessel–Viennot\;lemma
Lindstro¨m–Gessel–Viennotlemma，即
L
G
V
\rm LGV
LGV 引理，可以用来处理有向无环图(不准确，看下面的释疑)上不相交路径计数等问题。（有向无环图真的可行吗？）
前置知识：图、行列式。
定义
摘自OI Wiki.
ω
(
P
)
\omega(P)
ω(P) 表示
P
P
P 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为
1
1
1）（事实上，边权可以为生成函数）
e
(
u
,
v
)
e(u,v)
e(u,v) 表示
u
u
u 到
v
v
v 的 每一条 路径 P 的
ω
(
P
)
\omega(P)
ω(P) 之和，即
e
(
u
,
v
)
=
∑
P
:
u
→
v
ω
(
P
)
e(u,v)=\sum_{P:u\rightarrow v}\omega(P)
e(u,v)=∑P:u→vω(P) 。
起点集合
A
A
A，是有向无环图点集的一个子集，大小为
n
n
n。
终点集合
B
B
B，也是有向无环图点集的一个子集，大小也为
n
n
n。
一组
A
→
B
A\rightarrow B
A→B 的不相交路径
S
S
S：
S
i
S_i
Si 是一条从
A
i
A_i
Ai 到
B
σ
(
S
)
i
B_{σ(S)_i}
Bσ(S)i 的路径（
σ
(
S
)
σ(S)
σ(S) 是一个排列），对于任何
i
≠
j
i\not= j
i=j，
S
i
S_i
Si 和
S
j
S_j
Sj 没有公共顶点。
N
(
σ
)
N(σ)
N(σ) 表示排列
σ
σ
σ 的逆序对个数。
引理
∑
S
:
A
→
B
(
−
1
)
N
(
σ
(
S
)
)
∏
i
=
1
n
ω
(
S
i
)
=
∣
e
(
A
1
,
B
1
)
e
(
A
1
,
B
2
)
⋯
e
(
A
1
,
B
n
)
e
(
A
2
,
B
1
)
e
(
A
2
,
B
2
)
⋯
e
(
A
2
,
B
n
)
⋯
⋯
⋱
⋯
e
(
A
n
,
B
1
)
e
(
A
n
,
B
2
)
⋯
e
(
A
n
,
B
n
)
∣
\sum_{S:A\rightarrow B}(-1)^{N(σ(S))}\prod_{i=1}^{n}\omega(S_i)= \begin{vmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \cdots&\cdots&\ddots&\cdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\\ \end{vmatrix}
S:A→B∑(−1)N(σ(S))i=1∏nω(Si)=∣∣∣∣∣∣∣∣e(A1,B1)e(A2,B1)⋯e(An,B1)e(A1,B2)e(A2,B2)⋯e(An,B2)⋯⋯⋱⋯e(A1,Bn)e(A2,Bn)⋯e(An,Bn)∣∣∣∣∣∣∣∣
等式左边即为我们要求的方案数，OI Wiki：
∑
S
:
A
→
B
\sum_{S:A\rightarrow B}
∑S:A→B 为上文提到的每一组不相交路径
S
S
S.
可以发现，我们如果用高斯消元求行列式的值，解决这个问题的时间复杂度是
O
(
n
3
)
O(n^3)
O(n3) 的。
证明
参考维基百科（需要梯子）
翻译一下核心证明公式：（好像不是很核心）
det
M
=
∑
σ
∈
S
n
s
i
g
n
(
σ
)
∏
i
=
1
n
e
(
a
i
,
b
σ
(
i
)
)
=
∑
σ
∈
S
n
s
i
g
n
(
σ
)
∏
i
=
1
n
∑
P
i
:
a
i
→
b
σ
(
i
)
ω
(
P
i
)
=
∑
σ
∈
S
n
s
i
g
n
(
σ
)
∑
{
ω
(
P
)
:
P
从
(
a
1
,
a
2
,
…
,
a
n
)
到
(
b
σ
(
1
)
,
b
σ
(
2
)
,
…
,
b
σ
(
n
)
)
的
n
条
路
径
}
=
∑
{
s
i
g
n
(
σ
(
P
)
)
ω
(
P
)
:
P
扭曲的从
(
a
1
,
a
2
,
…
,
a
n
)
到
(
b
1
,
b
2
,
.
.
.
,
b
n
)
的
n
条路径
}
=
∑
{
s
i
g
n
(
σ
(
P
)
)
ω
(
P
)
:
P
扭曲的从
(
a
1
,
a
2
,
…
,
a
n
)
到
(
b
1
,
b
2
,
.
.
.
,
b
n
)
的
n
条 不相交 路径
}
+
∑
{
s
i
g
n
(
σ
(
P
)
)
ω
(
P
)
:
P
扭曲的从
(
a
1
,
a
2
,
…
,
a
n
)
到
(
b
1
,
b
2
,
.
.
.
,
b
n
)
的
n
条 存在相交 的路径
}
=
∑
(
P
1
,
…
,
P
n
)
:
A
→
B
s
i
g
n
(
σ
(
P
)
)
ω
(
P
)
+
∑
{
s
i
g
n
(
σ
(
P
)
)
ω
(
P
)
:
P
扭曲的从
(
a
1
,
a
2
,
…
,
a
n
)
到
(
b
1
,
b
2
,
.
.
.
,
b
n
)
的
n
条 存在相交 的路径
}
⏟
=
0
?
{\displaystyle {\begin{array}{rcl}\det M&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}\omega (P_{i})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\sum \{\omega (P):P~{\text从}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{到}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)~{\text的}~n~{\text条路径}\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{扭曲的从}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{到}}~\left(b_{1},b_{2},...,b_{n}\right)~{\text{的}}~n~{\text{条路径}}\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{扭曲的从}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{到}}~\left(b_{1},b_{2},...,b_{n}\right)~{\text{的}}~n~{\text{条 不相交 路径}}\}\\&&+\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{扭曲的从}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{到}}~\left(b_{1},b_{2},...,b_{n}\right)~{\text{的}}~n~{\text{条 存在相交 的路径}}\}\\&=&\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\omega (P)\\&&+\underbrace {\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{扭曲的从}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{到}}~\left(b_{1},b_{2},...,b_{n}\right)~{\text{的}}~n~{\text{条 存在相交 的路径}}\}} _{=0?}\\\end{array}}}
detM======∑σ∈Snsign(σ)∏i=1ne(ai,bσ(i))∑σ∈Snsign(σ)∏i=1n∑Pi:ai→bσ(i)ω(Pi)∑σ∈Snsign(σ)∑{ω(P):P 从 (a1,a2,…,an) 到 (bσ(1),bσ(2),…,bσ(n)) 的 n 条路径}∑{sign(σ(P))ω(P):P 扭曲的从 (a1,a2,…,an) 到 (b1,b2,...,bn) 的 n 条路径}∑{sign(σ(P))ω(P):P 扭曲的从 (a1,a2,…,an) 到 (b1,b2,...,bn) 的 n 条 不相交 路径}+∑{sign(σ(P))ω(P):P 扭曲的从 (a1,a2,…,an) 到 (b1,b2,...,bn) 的 n 条 存在相交 的路径}∑(P1,…,Pn):A→Bsign(σ(P))ω(P)+=0?
∑{sign(σ(P))ω(P):P 扭曲的从 (a1,a2,…,an) 到 (b1,b2,...,bn) 的 n 条 存在相交 的路径}
第一行是行列式的展开式，后面相当于把每种排列都枚举出来，“扭曲的(直译)”表示
a
i
a_i
ai 不一定对应
b
i
b_i
bi，其中的
s
i
g
n
(
σ
(
P
)
)
{\rm sign}(σ(P))
sign(σ(P)) 表示
(
−
1
)
排列 σ(P) 的逆序数
(-1)^{\text{排列 σ(P) 的逆序数}}
(−1)排列 σ(P) 的逆序数 。
那么，在
(
a
1
,
a
2
,
…
,
a
n
)
\left(a_{1},a_{2},\ldots ,a_{n}\right)
(a1,a2,…,an) 到
(
b
σ
(
P
)
1
,
b
σ
(
P
)
2
,
…
,
b
σ
(
P
)
n
)
\left(b_{σ(P)_1},b_{σ(P)_2},\ldots,b_{σ(P)_n}\right)
(bσ(P)1,bσ(P)2,…,bσ(P)n) 的
n
n
n 条路径中，这样的一个逆序代表什么？根据引子里的分析，我们不难发现一个逆序的产生就意味着两条路径相交，那么，根据容斥原理，不难发现上式底下那个大括号框出的式子是等于零的了！
例题
不管在有向无环图中是否可行，反正在网格图中是可行的。
下面看这道例题：
Gym102978A：Ascending Matrix
英文题解：
释疑
虽然都说是有向无环图适用，但是是事实是，我们会找到很多有向无环图，它们计算出的答案并不正确。
我们会发现一个规律：这些不适用的有向无环图都是三维图。
什么意思呢？也就是我们无法把所有点和边画在平面上，使得边之间不交叉。
这个定理的证明核心，其实是对于两对点
a
→
b
,
c
→
d
a\rightarrow b\;,\;c\rightarrow d
a→b,c→d ，交换
c
c
c 和
d
d
d 后不存在方案合法。如果是三维图的话，它们可以绕过去，像一上一下的立交桥一样。
而二维图就适用了，因为它和网格图性质是一样的。
扩展
如果真的是个三维图，那么求出来的是什么呢？
我们还是把整个图拍扁，把两条边交叉定义为在二维面上有交点。
永远的神 S
Y
\rm SY
SY 给出了答案：那就是【路径点不相交、边交叉对数为偶数的方案数】 减去 【路径点不相交、边交叉对数为奇数的方案数】。
刚好在 【NOI2021 D1T2 路径交点】 中被考到 (〒_〒)。
