LGV 引理

这个东西一般用来求 DAG 中从初始点集合 \(S\) 到终止点集合 \(T\) 的有符号不相交路径方案数（不相交指的是点不会同时出现在两个路径中），\(n=|S|=|T|\)。

设 \(P(w)\) 表示路径 \(w\) 上的边权的乘积，\(e(s,t)\) 表示 \(\sum_{w:s\to t}P(w)\)。

则：

其中 \(S\) 表示一组不相交路径，\(S_i:A_i\to B_{p_i}\)，\(N(p)\) 表示排列 \(p\) 的逆序对数。

【模板】LGV 引理

网格图中直接计算即可，显然 \(A_i\) 只会到达 \(B_i\)（\(A_i\) 和 \(B_i\) 均已排序），否则一定有交点，所以 \(N(p)\) 恒为 \(0\)，所以 \(\det(A)\) 即为答案。

// qwq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> arr;
typedef vector<arr> Arr;
constexpr int N=2e6+9,M=300;
constexpr int mo=998244353;
inline int Det(Arr a,int n){
    int ans=1,rev=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n&&!a[i][i];j++)
            if(a[j][i])a[i].swap(a[j]),rev^=1;
        if(!a[i][i])return 0;
        for(int j=i+1;j<=n;j++){
            if(a[j][i]>a[i][i])a[i].swap(a[j]),rev^=1;
            while(a[j][i]){
                int d=a[i][i]/a[j][i];
                for(int k=i;k<=n;k++)
                    a[i][k]=(a[i][k]-(ll)a[j][k]*d%mo+mo)%mo;
                a[i].swap(a[j]),rev^=1;
            }
        }
        ans=(ll)ans*a[i][i]%mo;
    }
    rev&&(ans=(mo-ans)%mo);
    return ans;
}
int fac[N],inv[N];
int C(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int T,n,m,a[M],b[M];
int main(){
    fac[0]=inv[0]=fac[1]=inv[1]=1;
    for(int i=2;i<N;i++)fac[i]=(ll)fac[i-1]*i%mo;
    for(int i=2;i<N;i++)inv[i]=(ll)(mo-mo/i)*inv[mo%i]%mo;
    for(int i=2;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mo;
    cin>>T;
    while(T--){
        cin>>n>>m;
        Arr s(m+1,arr(m+1,0));
        for(int i=1;i<=m;i++)
            cin>>a[i]>>b[i];
        sort(a+1,a+m+1),sort(b+1,b+m+1);
        for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)
            if(a[i]<=b[j])s[i][j]=C(b[j]-a[i]+n-1,n-1);
        cout<<Det(s,m)<<'\n';
    }
    return 0;
}

P7736 [NOI2021] 路径交点

假设 \(i<j\)，则 \(i\to x\) 和 \(j\to y\) 的路径间交点数之和的奇偶性和 \(x\) 和 \(y\) 的大小关系有关，与路径经过了哪些节点无关，若 \(x<y\) 则交点数之和为偶数，否则为奇数。所以一组不相交路径的交点数的奇偶性和其对应排列的逆序对的奇偶性相同，所以我们可以直接套用 LGV 引理即可。

// qwq
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> ar;
typedef vector<ar> arr;
typedef long long ll;
constexpr ll mo=998244353;
int Det(arr a,int n){
    int ans=1,rev=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n&&!a[i][i];j++)
            if(a[j][i]){a[i].swap(a[j]),rev^=1;}
        if(!a[i][i]) return 0;
        for(int j=i+1;j<=n;j++){
            if(a[j][i]>a[i][i])a[i].swap(a[j]),rev^=1;
            while(a[j][i]){
                int d=a[i][i]/a[j][i];
                for(int k=i;k<=n;k++)
                    a[i][k]=(a[i][k]-(ll)a[j][k]*d%mo+mo)%mo;
                a[i].swap(a[j]),rev^=1;
            }
        }
        ans=(ll)ans*a[i][i]%mo;
    }
    rev&&(ans=(mo-ans)%mo);
    return ans;
}
constexpr int N=103;
struct mat{
    int a[N<<1][N<<1],an,am;
    mat operator * (mat b){
        mat z;z.an=an,z.am=b.am;
        for(int i=1;i<=z.an;i++){
            for(int j=1;j<=z.am;j++){
                z.a[i][j]=0;
                for(int k=1;k<=am;k++)
                    z.a[i][j]=(z.a[i][j]+(ll)a[i][k]*b.a[k][j]%mo)%mo;
            }
        }
        return z;
    }
    void cls(int _n,int _m){
        an=_n,am=_m;
        for(int i=1;i<=_n;i++)
            for(int j=1;j<=_m;j++)
                a[i][j]=0;
    }
}A,B;
int T,n[N],m[N],K;
int main(){
    cin>>T;
    while(T--){
        cin>>K;
        for(int i=1;i<=K;i++)
            cin>>n[i];
        for(int i=1;i<K;i++)
            cin>>m[i];
        A.cls(n[1],n[1]);
        for(int i=1;i<=n[1];i++)
            A.a[i][i]=1;
        for(int i=1;i<K;i++){
            B.cls(n[i],n[i+1]);
            for(int j=1,x,y;j<=m[i];j++)
                cin>>x>>y,B.a[x][y]=1;
            A=A*B;
        }
        arr a(n[1]+1,ar(n[1]+1,0));
        for(int i=1;i<=n[1];i++)
            for(int j=1;j<=n[1];j++)
                a[i][j]=A.a[i][j];
        cout<<Det(a,n[1])<<'\n';
    }
    return 0;
}

本栏目推荐文章
• LGV 引理
• 【数学】LGV 引理
• LGV引理小记
• 【模板】图的计数相关：行列式及求值、Matrix-Tree 定理、BEST 定理、LGV 引理
• LGV引理
• 【学习笔记】LGV引理

LGV笔记lgv 数学lgv 小记lgv