P6657 【模板】LGV 引理 题解
littlez_meow
·
·
题解
感觉有的题解的双射构造稍微有一点点小问题啊。
题目指路。
Part 1：LGV 引理
定义
在有向无环图 G 中，定义：
$e(u,v)=\sum\limits_{Q:u\to v}\omega(Q)$，即所有 $u$ 到 $v$ 的路径的 $\omega$ 之和。若将边权设为重边个数，则其意义为 $u$ 到 $v$ 的路径数，乘法原理易证。
起点集合 $A=\{a_1,a_2,\cdots,a_n\}$，终点集合 $B=\{b_1,b_2,\cdots,b_n\}$。
路径 $P_i$ 为从 $a_i$ 到 $b_{\sigma_i}$ 的路径，其中 $\sigma$ 为 $1\sim n$ 的全排列之一。
$I(\sigma)$ 为排列 $\sigma$ 的逆序对数。
路径组 $P=\{P_1,P_2,\cdots,P_n\}$，记为 $P:A\to B$。（相交或不相交请见上下文表述）
$\omega(P)=\prod\limits_{i=1}^n\omega(P_i)
，即路径组 P 中所有路径的权值积。
可以发现，排列 \sigma 是 P 的函数。记 P 对应的排列为 \pi(P)。（改个符号以免看晕了）
内容
记矩阵 M=\begin{bmatrix}
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)\\
\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\to B}(-1)^{I(\pi(S))}\prod\limits_{i=1}^n\omega(P_i)。
此处 S 为不相交路径组。
当边权为重边个数时，其意义为逆序对为偶数的不相交路径组数减逆序对为奇数的不相交路径组数。
证明
根据定义展开行列式，等式左边为：
\sum\limits_{\sigma}(-1)^{I(\sigma)}\prod\limits_{i=1}^n e(a_i,b_{\sigma_i})
再拆开 e(u,v)，得：
\sum\limits_{\sigma}(-1)^{I(\sigma)}\prod\limits_{i=1}^n\sum\limits_{T_i:a_i\to b_{\sigma_i}}\omega(T_i)
我们发现，T=\{T_1,T_2,\cdots,T_n\} 是一个路径组，且 \pi(T)=\sigma。因此将枚举排列变为枚举路径组，这样就不用再次枚举路径 T_i，得到：
\sum\limits_{T:A\to B}(-1)^{I(\pi(T))}\prod\limits_{i=1}^n\omega(T_i)
此处 T 为任意路径组。
现在，等式左右唯一区别为，等式左边是不相交路径组，等式右边是任意路径组。
记 K,L 分别为相交、不相交路径组，有 K\cap L=\varnothing,K\cup L=T，所以得：
\sum\limits_{K:A\to B}(-1)^{I(\pi(T))}\prod\limits_{i=1}^n\omega(T_i)+\sum\limits_{L:A\to B}(-1)^{I(\pi(T))}\prod\limits_{i=1}^n\omega(T_i)
我们仅需证明 \sum\limits_{K:A\to B}(-1)^{I(\pi(T))}\prod\limits_{i=1}^n\omega(T_i)=0 即可。
记相交路径组的集合为 C，我们只要构造一个双射 f:C\to C 使得 \forall K\in C,(-1)^{I(\pi(K))}\times(-1)^{I(\pi(f(K)))}=-1,\omega(K)=\omega(f(k))，就可以得到求和式中所有正数项都有一个绝对值相等的负数项与之一一对应，和相互抵消成 0。
问题就转化为了构造这个双射。
让我们先尝试用这篇题解的方式构造：
-
选择最小的二元组 (i,j) 满足 P_i 和 P_j 相交。
-
将 P_i,P_j 交换首个交点到末尾的这部分路径，得到 P'。
-
此时 \pi(P') 相当于 \pi(P) 进行了一次对换，逆序对个数奇偶性改变。
-
这样，就构造出了双射……吗？
让我们看看下面的例子：
选择到最小二元组 (1,3)。
交换后得到下图：
此时再次选择，得到的是 (1,2) 而非 (1,3)！
也就是说，这样无法构造出双射！
我们应该换一种方法选择二元组。
观察上面的图片，我们能发现，在 $j$ 变小的时候，交点会变远。简单想想就会发现这个是事实。因为若交点更近，第一次就会选到。（语文不好，感性理解理解，画画图）
所以，我们选择最小的 $i$ 使 $p_i$ 与别的路径有交点，再选择 $j$ 使得其交点离出发点 $a_i$ 最近，若有多个再选最小的 $j$，这样得到的 $(i,j)$ 就可以成为双射。
自此，证明结束。
## Part 2：本题
题目中给了 $a_1\le a_2\le\cdots\le a_m,b_1\le b_2\le\cdots\le b_m$，若路径不相交，就只能从 $(a_i,1)$ 到 $(b_i,n)$，也就是说 $\pi(S)$ 始终为 $1,2,\cdots,n$，逆序对为 $0$。因此，$(-1)^{I(\pi(S))}$ 没有任何影响，直接求行列式即可。
至于 $e(a_i,b_j)$，为网格图上最短路径总数，相当于从 $b_j-a_i+n-1$ 段中选 $n-1$ 段向右走。故 $e(a_i,b_j)=\binom{b_j-a_i+n-1}{n-1}$。
## Part 3：代码
```cpp
#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define _ 0
using namespace std;
const int MAX=101,MOD=998244353;
int n,m,T;
int a[101],b[101],M[101][101];
int fact[2000001],inv[2000001];
inline ll det(int t[MAX][MAX],int len,const int mod=MOD){
ll res(1);
F(i,1,len-1){
F(j,i+1,len){
while(t[i][i]){
int delta=t[j][i]/t[i][i];
F(k,i,len) t[j][k]=(t[j][k]-(ll)delta*t[i][k]%mod+mod)%mod;
swap(t[i],t[j]);
res=~res+1;
}
swap(t[i],t[j]);
res=~res+1;
}
}
F(i,1,len) res=res*t[i][i]%mod;
return (res%mod+mod)%mod;
}
inline ll qpow(ll base,int expo){
ll res(1);
while(expo){
if(expo&1) res=res*base%MOD;
base=base*base%MOD;
expo>>=1;
}
return res;
}
inline ll C(int x,int y){
return x>=y?1ll*fact[x]*inv[y]%MOD*inv[x-y]%MOD:0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
fact[0]=inv[0]=1;
F(i,1,2000000) fact[i]=1ll*i*fact[i-1]%MOD;
inv[2000000]=qpow(fact[2000000],MOD-2);
R(i,2000000-1,1) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
for(cin>>T;T;--T){
cin>>n>>m;
F(i,1,m) cin>>a[i]>>b[i];
F(i,1,m) F(j,1,m) M[i][j]=C(b[j]-a[i]+n-1,n-1);
cout<<det(M,m)<<endl;
}
return ~~(0^_^0);
}
```
不喜勿喷qaq~