LGV引理
定义 \(A\) 是起点集合 \(\{a_1,a_2,...,a_n\}\) 。
\(B\) 是终点集合 \(\{b_1,b_2,...,b_n\}\)。
定义 \(\omega(P)\) 为路径 \(P\) 每一条边权值的乘积,即 :
\[\omega(P) = \prod_{e \in P}w_e
\]
定义 \(e(a,b)\) 表示点 \(a\rightarrow b\) 所有路径 \(P\) 的 \(\omega(P)\) 之和,即:
\[e(a,b) = \sum_{P:a \rightarrow b}\omega(P)
\]
定义 \(\sigma\) 为 \(1 \sim n\) 的一个任意全排列,定义 \(P_i\) 代表 \(a_i\rightarrow b_{\sigma_i}\) 一条路径。
设一个从 \(A\) 到 \(B\) 的路径集合 \(L=\{P_1,P_2,P_3,...,P_n\}\) 。
注意当 \(\sigma\) 一定时,路径集合 \(L\) 可能不同( \(a_i\rightarrow b_{\sigma(i)}\) 可能有多条路径)
(集合名称写成 \(L\) 是为了避免后文出现歧义)。
定义 \(t(L)\) 为关于路径集合 \(L\) 的全排列 \(\sigma\) 逆序对个数。
则定义:
\[\omega(L) = \prod_{P \in L}\omega(P)
\]
那我们可以知道逆序对是偶数路径条数 \(-\) 逆序对是奇数路径条数答案是:
\[\sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{i = 1}^n\omega(P_i)
\]
\(L\) 是路径均不相交的路径集合。
这个答案如何求呢?
设矩阵:
\[M = \begin{matrix}
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)\\
\vdots~~~~~~~~~~~~~~~\vdots~~~~~~~~~~~~~~~~~~~~\vdots\\
e(a_n,b_1)~~e(a_n,b_2)~...~e(a_n,b_n)\\
\end{matrix}
\]
其实矩阵行列式就是答案:
\[det(M) = \sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{P_i \in L}\omega(P_i)
\]
如何证明?
先考虑行列式的定义。
\[det(M) = \sum_{\sigma}(-1)^{t(\sigma)}\prod_i^ne(a_i,b_{\sigma(i)})
\]
根据上文 \(e(a,b)\) 定义推导一下。
\[det(M) = \sum_{\sigma}(-1)^{t(\sigma)}\prod_i^n\sum_{P_j:a_i
\rightarrow b_{\sigma(i)}}\omega(P_j)
$$\]
$$
> 此处 $L$ 为任意路径集合
设 ![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7 "U")$U$ 为不相交路径组,![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7 "V")$V$ 为相交路径组。
$$
\sum_{L:A\rightarrow B}(-1)^{t(\sigma)}\prod_{P_i \in L}\omega(P_i)
$$$$
=\sum_{U:A\rightarrow B}(-1)^{t(\sigma)}\prod_{U_i \in U}\omega(U_i) +
\sum_{V:A\rightarrow B}(-1)^{t(\sigma)}\prod_{V_i \in V}\omega(V_i)
$$
假设一对相交路径:
$$
a_i \rightarrow u \rightarrow b_i~~~~~~~~~~~a_j \rightarrow u \rightarrow b_j
$$
必定存在一对相交路径:
$$
a_i \rightarrow u \rightarrow b_j~~~~~~~~~~a_j \rightarrow u \rightarrow b_i
$$
逆序对个数差 $1$ ,一个为正一个为负抵消。
于是
$$
\sum_{V:A\rightarrow B}(-1)^{t(\sigma)}\prod_{V_i \in V}\omega(V_i) = 0\\
\Rightarrow \sum_{L:A\rightarrow B}(-1)^{t(\sigma)}\prod_{P_i \in L}\omega(P_i)
=\sum_{U:A\rightarrow B}(-1)^{t(\sigma)}\prod_{U_i \in U}\omega(U_i)
$$
得证
$$
det(M) = \sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{P_i \in L}\omega(P_i)
$$
## P6657 【模板】LGV 引理 题解
### 题意描述
$n \times n$ 棋盘,$m$ 个棋子,,第 $i$ 个棋子一开始放在 $(a_i,1)$ ,最终要走到 $(b_i,n)$。问有多少种方案,路径不能相交,求方案数。
保证 $1≤a_1≤a_2≤⋯≤a_m≤n,1≤b_1≤b_2≤⋯≤b_m≤n。$
### 题解
看到不相交,一眼 LGV ,我们看到保证部分,就可以知道他求的是逆序对数量为 0 的路径条数。并且有逆序对数量的路径条数一定为 0 ,就直接套模板了。
特别的,算 $e(a_i,b_j)$ 可以通过 $\binom {n - 1 + b_j - a_i} {n - 1}$。
原理是有 $n-1$ 条竖着走,有 $b_j - a_i$ 条横着走,求一下组合数就可以了。
### 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 10, M = 110,mod = 998244353;
int t, n, m, a[M], b[M];
ll pr[N], inv[N], s[M][M];
ll mpow(ll x, ll k)
{
ll ans = 1;
while(k)
{
if(k & 1) ans = ans * x % mod;
x = x * x % mod;
k >>= 1;
}
return ans;
}
void pre()
{
pr[0] = 1;
for(int i = 1; i <= N - 10; ++i)
pr[i] = pr[i - 1] * i % mod;
inv[N - 10] = mpow(pr[N - 10], mod - 2);
for(int i = N - 11; i >= 0; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline ll C(int a,int b)
{
if(a < b) return 0;
return pr[a] * inv[b] % mod * inv[a - b] % mod;
}
void input(){
cin>>n>>m;
for(int i = 1; i <= m; ++i)
cin>>a[i]>>b[i];
for(int i = 1; i <= m; ++i){
for(int j = 1; j <= m; ++j){
s[i][j] = C(n - 1 + b[j] - a[i],n - 1);
// cout<<s[i][j]<<' ';
}
// cout<<'\n';
}
}
ll op(){
ll w = 1;
for(int i = 1; i <= m; ++i){
for(int j = i + 1; j <= m; ++j){
while(s[i][i]){
ll d = s[j][i] / s[i][i];
for(int k = i; k <= m; ++k){
s[j][k] = (s[j][k] - s[i][k] * d % mod + mod) % mod;
}
swap(s[i], s[j]);
w = -w;
}
swap(s[i], s[j]);
w = -w;
}
}
w = (w + mod) % mod;
for(int i = 1; i <= m; ++i){
w = w * s[i][i] % mod;
}
return w;
}
int main(){
pre();
cin>>t;
while(t--){
// qk();
input();
cout<<op()<<'\n';
}
return 0;
}
```