基础知识
LGV 引理仅适用于有向无环图。
定义 $\omega (P)$ 为路径 $P$ 上每条边边权之积。
定义 $w(u,v)$ 为从 $u$ 到 $v$ 的每条路径 $P$ 的 $\omega (p)$ 之和。
现在有一个起点集合 $A$ 与终点集合 $B$，定义矩阵 $M$：
$$
M=
\begin{bmatrix}
w(1,1) & w(1,2) & \cdots & w(1,n) \\
w(2,1) & w(2,2) & \cdots & w(2,n) \\
\vdots & \vdots & \ddots & \vdots \\
w(n,1) & w(n,2) & \cdots & w(n,n) \\
\end{bmatrix}
$$
那么矩阵 $M$ 的行列式就是每一种互不相交的路径权值和的总和。
如果是路径计数问题的话，可以把边权都设为 $1$。
题目
P6657 【模板】LGV 引理
模板题。
显然 $e(u,v)$ 就是我们熟悉的方格路径计数问题，可以用组合数解决。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
const int mod=998244353;
int inv[N],jie[N];
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
void init(){
jie[0]=1;
for(int i=1;i<N;i++) jie[i]=(jie[i-1]*i)%mod;
inv[N-1]=qpow(jie[N-1],mod-2);
for(int i=N-1;i>0;i--) inv[i-1]=(inv[i]*i)%mod;
}
int C(int n,int m){
return ((jie[m]*inv[n])%mod*inv[m-n])%mod;
}
int det(vector<vector<int>> a,int n){
int res=1,f=1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
while(a[j][i]){
int t=a[i][i]/a[j][i];
for(int k=i;k<=n;k++) (a[i][k]+=mod-(t*a[j][k])%mod)%=mod;
swap(a[i],a[j]);
f=-f;
}
}
(res*=a[i][i])%=mod;
}
return ((res*f)%mod+mod)%mod;
}
void solve(){
int n,m;
cin>>n>>m;
vector<int> a(m+1),b(m+1);
vector<vector<int>> l(m+1,vector<int>(m+1,0));
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++){
if(b[j]<a[i]) l[i][j]=0;
else l[i][j]=C(n-1,n-1+b[j]-a[i]);
}
cout<<det(l,m)<<"\n";
}
signed main(){
int T;
cin>>T;
init();
while(T--) solve();
return 0;
}
Comments NOTHING