LGV 引理学习笔记

2026年8月26日 ooliver OI

基础知识

LGV 引理仅适用于有向无环图。

定义 $ω (P)$ 为路径 $P$ 上每条边边权之积。

定义 $w (u, v)$ 为从 $u$ 到 $v$ 的每条路径 $P$ 的 $ω (p)$ 之和。

现在有一个起点集合 $A$ 与终点集合 $B$ ，定义矩阵 $M$ ：

$M = [\begin{matrix} w (1, 1) & a m p; w (1, 2) & a m p; \dots & a m p; w (1, n) \\ w (2, 1) & a m p; w (2, 2) & a m p; \dots & a m p; w (2, n) \\ ⋮ & a m p; ⋮ & a m p; ⋱ & a m p; ⋮ \\ w (n, 1) & a m p; w (n, 2) & a m p; \dots & a m p; w (n, n) \end{matrix}]$

那么矩阵 $M$ 的行列式就是每一种互不相交的路径权值和的总和。

如果是路径计数问题的话，可以把边权都设为 $1$ 。

题目

P6657 【模板】LGV 引理

模板题。

显然 $e (u, v)$ 就是我们熟悉的方格路径计数问题，可以用组合数解决。

代码：

C++

#include
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;i0;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> a,int n){
    int res=1,f=1;
    for(int i=1;i>n>>m;
    vector a(m+1),b(m+1);
    vector> l(m+1,vector(m+1,0));
    for(int i=1;i>a[i]>>b[i];
    for(int i=1;i>T;
    init();
    while(T--) solve();
    return 0;
}

`#include
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;iN;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(vectorvectorint>> a,int n){
    int res=1,f=1;
    for(int i=1;in;i++){
        for(int j=i+1;jn;j++){
            while(a[j][i]){
                int t=a[i][i]/a[j][i];
                for(int k=i;kn;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;
    vectorint> a(m+1),b(m+1);
    vectorvectorint>> l(m+1,vectorint>(m+1,0));
    for(int i=1;im;i++) cin>>a[i]>>b[i];
    for(int i=1;im;i++) for(int j=1;jm;j++){
        if(b[j]a[i]) l[i][j]=0;
        else l[i][j]=C(n-1,n-1+b[j]-a[i]);
    }
    coutdet(l,m)"\n";
}

signed main(){
    int T;
    cin>>T;
    init();
    while(T--) solve();
    return 0;
}`

CF348D Turtles

一共两只乌龟，都从 $(1, 1)$ 出发，那肯定一只的路线是 $(1, 1) \to (1, 2) \to . . . \to (n - 1, m) \to (n, m)$ ，一只的路线是 $(1, 1) \to (2, 1) \to . . . \to (n, m - 1) \to (n, m)$ 。

那我们可以把 $(1, 2), (1, 2)$ 看作起点集合，把 $(n - 1, m), (n, m - 1)$ 看作终点集合，之后就是 LGV 引理板子了。

代码：

C++

#include
using namespace std;
#define int long long

const int N=3005;
const int mod=1e9+7;
int n,m;
int a[N][N],dp[N][N];

int det(vector> a,int n){
    int res=1,f=1;
    for(int i=1;i> l(3,vector(3,0));
    cin>>n>>m;
    for(int i=1;i>c;
        a[i][j]=(c=='#');
    }
    dodp(1,2);
    l[1][1]=dp[n-1][m],l[1][2]=dp[n][m-1];
    dodp(2,1);
    l[2][1]=dp[n-1][m],l[2][2]=dp[n][m-1];
    cout

`#include
using namespace std;
#define int long long

const int N=3005;
const int mod=1e9+7;
int n,m;
int a[N][N],dp[N][N];

int det(vectorvectorint>> a,int n){
    int res=1,f=1;
    for(int i=1;in;i++){
        for(int j=i+1;jn;j++){
            while(a[j][i]){
                int t=a[i][i]/a[j][i];
                for(int k=i;kn;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 dodp(int x,int y){
    memset(dp,0,sizeof dp);
    if(a[x][y]) return;
    dp[x][y]=1;
    for(int i=x;in;i++) for(int j=y;jm;j++){
        if(a[i][j]||(i==x&&j==y)) continue;
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    vectorvectorint>> l(3,vectorint>(3,0));
    cin>>n>>m;
    for(int i=1;in;i++) for(int j=1;jm;j++){
        char c;
        cin>>c;
        a[i][j]=(c=='#');
    }
    dodp(1,2);
    l[1][1]=dp[n-1][m],l[1][2]=dp[n][m-1];
    dodp(2,1);
    l[2][1]=dp[n-1][m],l[2][2]=dp[n][m-1];
    coutdet(l,2)"\n";
    return 0;
}`