笔记 算法 行列式——矩阵树与 LGV
行列式
单位矩阵的行列式为 $1$。
交换一个矩阵的两行或两列，其行列式改变符号。
将一个矩阵的某行或者某列乘以 $k$，其行列式也乘以 $k$。
将一个矩阵的某行或者某列乘以同个一数后加到另一行或一列后，其行列式不变。
矩阵 $A$ 的行列式为 $\det A$，必须满足矩阵的行列数量相同才有行列式。
\[\det A=\sum\limits_{j_1,j_2,\cdots,j_n\in \mathfrak S_n}(-1)^{\pi(j_1,j_2,\cdots,j_n)}a_{1,j_1}a_{2,j_2}\cdots a_{n,j_n}\]其中 $\pi(j_1,j_2,\cdots,j_n)$ 是 $j_1,j_2,\cdots,j_n$ 的逆序对数。
对于模数非质数的情况，用类似 $\gcd$ 的方法，具体见代码，其实只把 if 换成了 while，把模意义除法换成了下取整除法再减法，多次进行变成 $0$。
P7112 【模板】行列式求值
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=607;
int n,P;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return d?P-d:0;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
mint a[N][N];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>P;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
cin>>a[i][j],a[i][j].d%=P;
mint ans=1;
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
while(a[i][i].d){
int x=a[j][i].d/a[i][i].d;
for(int k=i;k<=n;k++)
a[j][k]-=x*a[i][k];
swap(a[i],a[j]);
ans=-ans;
}
swap(a[i],a[j]);
ans=-ans;
}
for(int i=1;i<=n;i++)
ans*=a[i][i];
cout<<ans<<'\n';
return 0;
}
矩阵树
给定一张 n 个结点 m 条边的带权图（可能为无向图，可能为有向图）。定义其一个生成树 $T$ 的权值为 $T$ 中所有边权的乘积（有向图钦定根为 $1$）。求其所有不同生成树的权值之和。
权值之和为 $\det A$，其中 $A$ 是 $D-C$ 后删去根所在的那行和那列（如果是无根树则删去任意一点所在的行列均可），其中 $D$ 为度数矩阵，$C$ 为邻接矩阵。
无向图：
若存在边 $(x,y,z)$，则对 $D_{x,x}$ 贡献是 $z$，对 $D_{y,y}$ 贡献是 $z$。
若存在边 $(x,y,z)$，则对 $C_{x,y}$ 贡献是 $z$，对 $C_{y,x}$ 贡献是 $z$。
有向图：
若存在边 $(x,y,z)$，则对内向树 $D_{x,x}$ 贡献是 $z$，对外向树 $D_{y,y}$ 贡献是 $z$。
若存在边 $(x,y,z)$，则对内向树和外向树的 $C_{x,y}$ 贡献均是 $z$。
感性证明：首先考虑 $j_k=k$ 的情况，那就相当于把 $A$ 的对角线乘起来，对角线上是每个点的度数，每个点随机连一条边，会形成若干基环树。如果我删去根所在的那行那列，就形成了若干基环树和一颗树。那就是容斥，容斥系数是 $-1$ 的环个数次。注意到行列式上排列的逆序对数与是形成非自环的环数量的奇偶性相同，所以可证。
P6178 【模板】Matrix-Tree 定理
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=307,P=1e9+7;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return d?P-d:0;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n,m,T;
mint a[N][N];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m>>T;
if(T==0){
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
a[u][u]+=w;a[v][v]+=w;
a[u][v]-=w;a[v][u]-=w;
}
}else{
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
a[v][v]+=w;
a[u][v]-=w;
}
}
mint ans=1;
for(int i=2;i<=n;i++)for(int j=i+1;j<=n;j++){
if(a[i][i].d){
mint x=a[j][i]/a[i][i];
for(int k=i;k<=n;k++)
a[j][k]-=x*a[i][k];
swap(a[i],a[j]);
ans=-ans;
}
swap(a[i],a[j]);
ans=-ans;
}
for(int i=2;i<=n;i++)
ans*=a[i][i];
cout<<ans<<'\n';
return 0;
}
LGV
在一个 DAG 中，有 $2n$ 个点 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots,b_n$。
定义路径组为 $n$ 条路径，第 $i$ 条路径是 $a_i\to b_{j_i}$ 每条路径互相不交，每条路径的权值为 $(-1)^k$，其中 $k$ 为 $j_1,j_2,\cdots,j_n$ 的逆序对个数。
令 $a_{i,j}$ 为 $a_i\to b_j$ 的路径数量。那么 $A$ 的行列式 $\det A$ 即为所有路径的权值和。
如果我们让符合要求的匹配只有一组，即 $j_i=i$ ，那么求出来的就是 $a_i\to b_i$，并且所有路径不相交的方案数。
P6657 【模板】LGV 引理
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=2e6+7,M=107,P=998244353;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return d?P-d:0;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n,m,a[N],b[N];
mint fac[N],inv[N];
mint f[M][M];
mint Bi(int x,int y){
if(x<y)return 0;
return fac[x]*inv[y]*inv[x-y];
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<N;i++)fac[i]=fac[i-1]*i;
inv[N-1]=fac[N-1].inv();
for(int i=N-2;i>1;i--)inv[i]=inv[i+1]*(i+1);
int T;cin>>T;while(T--){
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
f[i][j]=Bi(m-1+b[j]-a[i],m-1);
mint ans=1;
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
if(f[i][i].d){
auto x=f[j][i]/f[i][i];
for(int k=i;k<=n;k++)
f[j][k]-=x*f[i][k];
swap(f[i],f[j]);
ans=-ans;
}
swap(f[i],f[j]);
ans=-ans;
}
for(int i=1;i<=n;i++)
ans*=f[i][i];
cout<<ans<<'\n';
}
return 0;
}
P7736 [NOI2021] 路径交点
对于本题，会发现路径交叉奇偶性与最后逆序对数量奇偶性相同。
于是只要 bfs 处理出第一列每个点到最后一列每个点的方案数即可。
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=207,P=998244353;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return d?P-d:0;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int k,n[N],m[N];
mint a[N][N],f[N][N];
queue<pii>q;
vector<pii>g[N][N];
bool vis[N][N];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;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];
for(int j=1;j<=m[i];j++)
g[i][j].clear();
}
for(int i=1;i<k;i++){
for(int j=1,u,v;j<=m[i];j++){
cin>>u>>v;
g[i][u].emplace_back(i+1,v);
}
}
for(int p=1;p<=n[1];p++){
memset(f,0,sizeof f);
memset(vis,0,sizeof vis);
q.emplace(1,p);
f[1][p]=1;
while(!q.empty()){
auto[id1,u]=q.front();q.pop();
for(auto[id2,v]:g[id1][u]){
assert(id2<=k);
f[id2][v]+=f[id1][u];
if(!vis[id2][v]){
q.emplace(id2,v);
vis[id2][v]=true;
}
}
}
for(int i=1;i<=n[1];i++)
a[p][i]=f[k][i];
}
mint ans=1;
for(int i=1;i<=n[1];i++)for(int j=i+1;j<=n[1];j++){
if(a[i][i].d){
auto x=a[j][i]/a[i][i];
for(int k=i;k<=n[1];k++)
a[j][k]-=x*a[i][k];
swap(a[i],a[j]);
ans=-ans;
}
swap(a[i],a[j]);
ans=-ans;
}
for(int i=1;i<=n[1];i++)
ans*=a[i][i];
cout<<ans<<'\n';
}
return 0;
}