基础知识 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 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;inm; vector a(m+1),b(m+1); vector l(m+1,vector(m+1,0)); for(int i=1;ia[i]b[i]; for(int i=1;iT; 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;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(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; cinnm; vectorint a(m+1),b(m+1); vectorvectorint l(m+1,vectorint(m+1,0)); for(int i=1;im;i++) cina[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; cinT; 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 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)); cinnm; for(int i=1;ic; 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)); cinnm; for(int i=1;in;i++) for(int j=1;jm;j++){ char c; cinc; 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; }
LGV 引理学习笔记
ooliver