基础知识
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;
}CF348D Turtles
一共两只乌龟，都从 $(1,1)$ 出发，那肯定一只的路线是 $(1,1)\rightarrow (1,2)\rightarrow ...\rightarrow (n-1,m)\rightarrow (n,m)$，一只的路线是 $(1,1)\rightarrow (2,1)\rightarrow ...\rightarrow (n,m-1)\rightarrow (n,m)$。
那我们可以把 $(1,2),(1,2)$ 看作起点集合，把 $(n-1,m),(n,m-1)$ 看作终点集合，之后就是 LGV 引理板子了。
代码：
C++
#include<bits/stdc++.h>
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<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 dodp(int x,int y){
memset(dp,0,sizeof dp);
if(a[x][y]) return;
dp[x][y]=1;
for(int i=x;i<=n;i++) for(int j=y;j<=m;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);
vector<vector<int>> l(3,vector<int>(3,0));
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;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];
cout<<det(l,2)<<"\n";
return 0;
}
Comments NOTHING