基础知识 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;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)\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)); 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; }`
LGV 引理学习笔记
笔记