• 欢迎光临~

LGV 引理

开发技术 开发技术 2022-06-05 次浏览

(LGV) 引理

在有向无环图中,有一组起点 (A = {a_1,a_2……a_n })终点 (B={b_1,b_2……b_n })

定义 (w(P)) 为一条路径 (P) 中每条边权的乘积,即 (w(P)=prod_{ein P}v_e)

定义 (e(a,b)) 为两点之间所有路径的 (w) 之和,即 (e(a,b)=sum_{P:a->b} w(P))

设一个从 (A)(B) 的路径组为 (P=(P_1,P_2……P_n),P_i = (a_i,b_{r(i)})),其中 (r) 为任意一个 (1)(n) 的排列。

则定义 (w(P)=prod_{i = 1}^n w(P_i))

定义 (t(P)) 为该路径对应的排列 (r) 的逆序对数。

那么 (LGV) 引理描述为,设一个矩阵

[M = begin{pmatrix}e(a_1,a_2) e(a_1,b_2) … e(a_1,b_n)\ e(a_2,b_1) e(a_2,b_2) … e(a_2,b_n) \ …… \ e(a_n,b_1) e(a_n,b_2) … e(a_n,b_n) end{pmatrix} ]

则有定理

(det(M)=sum_{P:A->B} (-1)^{t(P)} prod_{i=1}^n w(P_i))

其中 (P) 是一个从 (A)(B) 的不相交路径组。

该定理的实际意义为,(det(M)) 的值是所有不相交路径组方案数的带符号数量和。

证明:

由行列式定义知

[det(M) = sum_{r} (-1)^{tau (r)}prod _{i =1}^n e(a_i,b_{r_i}) = sum_{r}(-1)^{tau (r)}prod_{i=1}^n sum_{P:a_i->b_{r_i}} w(P) ]

观察 (prod_{i=1}^n sum_{P:a_i->b_{r_i}} w(P)),实际上是所有从 (A)(B) 排列为 (r) 的路径组 (P)(w(P)) 之和。

(sum_r (-1)^{tau (r)}prod_{i=1}^n sum_{P:a_i->b_{r_i}}w(P) = sum_r (-1)^{tau (r)}sum_{P=r}w(P)=sum_{P:A->B}(-1)^{t(P)}prod_{i=1}^n w(P_i))

实际上,这里的 (P) 是一个任意路径组,描述的并非不相交路径组

(U) 为不相交路径组,(V) 为相交路径组,则:

[sum_{P:A->B}(-1)^{t(P)}prod_{i=1}^n w(P_i) = sum_{U:A->B} (-1)^{t(U)}prod_{i=1}^n w(U_i)+sum_{V:A->B}(-1)^{t(V)}prod_{i=1}^n w(V_i) ]

只需证

[sum_{V:A->B}(-1)^{t(V)}prod_{i=1}^n w(V_i) = 0 ]

定理即得证。

实际上,我们在一组相交路径 (P) 中取一个相交路径中最小的二元组 ((i,j))

有路径 (P_i:a_1->u->b_1,P_j=a_2->u->b_2)

稍作更改,可得 (P_i:a_1->u->b_2,P_j=a_2->u->b_1),我们通过这种构造得到一组新的相交路径 (P'),容易发现:

[w(P) = w(P'),t(P)=t(P')±1 ]

对于任意相交路径,都能通过这样的交换使其一一对应,相互抵消,故而引理得证。

例题

(CF348D) (Turtles)

一张 (n)(m) 列的网格图,图的某些格子上有障碍物,求出满足 ((1,1))((n,m)) 的两条不相交且均不经过障碍物的路径个数,答案对 (10^9 +7) 取模,((x,y)) 一步只能到达 ((x +1,y))((x,y+1))

(2leq n,mleq 3times 10^3)

(Sol)

看到不相交,考虑 (LGV) 引理。

因为所有路径不能在起点终点处相交,选定起点集合 (A={(1,2),(2,1) }),终点集合 (B={(n-1,m),(m-1,n) }) ,边权均设为 (1)。跑 (LGV) 引理即可,其中 (e_{i,j}) 可以通过 (dp) 求解。此时 (det(M)) 即为答案,这样做是对的原因是因为当且仅当 (r=(1,2)) 时路径才不会交叉,此时 (tau(r)=1)。时间复杂度 (O(nm))

(code)

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10, mod = 1e9 + 7;
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
char mp[N][N];
int n, m, dp[N][N];
inline int f(int x1, int y1, int x2, int y2)
{
	if(mp[x1][y1] == '#' || mp[x2][y2] == '#') return 0;
	memset(dp, 0, sizeof(dp)), dp[x1][y1] = 1;
	for(register int i = 1; i <= x2; i++)
		for(register int j = 1; j <= y2; j++)
			if(mp[i][j] == '.') (dp[i][j] += dp[i - 1][j]) %= mod, (dp[i][j] += dp[i][j - 1]) %= mod;
	return dp[x2][y2];
}
int main()
{
	n = read(), m = read();
	for(register int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
	int f11 = f(1, 2, n - 1, m), f12 = f(1, 2, n, m - 1), f21 = f(2, 1, n - 1, m), f22 = f(2, 1, n, m - 1);
	int ans = ((1ll * f11 * f22 % mod - 1ll * f21 * f12 % mod) % mod + mod) % mod;
	printf("%dn", ans);
	return 0;
}

(LuoGu P6657) ([)模板(]) (LGV) 引理

(T) 组数据,每组给出一个 (ntimes n) 的棋盘,棋子从 ((x,y)) 一步只能走到 ((x+1,y))((x,y+1)) ,有 (m) 个棋子,初始时第 (i) 个放在 ((1,a_i)),有 (m) 个终点,第 (i) 个终点是 ((n,b_i)) 。求出有多少种方案,能使每个棋子都能从起点走到终点,且对于所有的棋子它们的路径不交,答案对 (998244353) 取模。

(1leq Tleq 5,2leq nleq 10^6,1leq mleq 100,1leq a_1leq a_2leq … leq a_mleq n,1leq b_1 leq b_2leq … leq b_m leq n)

(Sol)

不相交路径,考虑 (LGV) 引理。

注意到对于本题,只有当 (r=(1,2…m)) 时才能找到这样的路径,此时 (tau(r) = 1),可以套用 (LGV) 引理直接做。对于 (e_{a_i,b_j}) 它等于:

[e_{a_i,b_j} = begin{Bmatrix}binom{b_j-a_i+n-1}{n-1} b_jgeq a_i \ 0 otherwise end{Bmatrix} ]

设边权为 (1),预处理阶乘(组合数),求出 (M) 矩阵后直接做行列式就是答案,理由与上个题目相似,时间复杂度 (O(Tm^3+n))

(code)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e2 + 10, N = 2e6 + 10, lim = 2e6, mod = 998244353;
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
int T, n, m;
int x[M], y[M], e[M][M];
int fac[N], inv[N];
inline int power(int x, int k)
{
	int res = 1;
	while(k){
		if(k & 1) res =  res * x % mod;
		x = x * x % mod, k >>= 1;
	}
	return res;
}
inline void initial()
{
	fac[0] = inv[0] = 1;
	for(register int i = 1; i <= lim; i++) fac[i] = fac[i - 1] * i % mod;
	inv[lim] = power(fac[lim], mod - 2);
	for(register int i = lim - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline int C(int x, int y) { return x < y ? 0 : fac[x] * inv[y] % mod * inv[x - y] % mod; }
inline int det()
{
	int res = 1, f = 1;
	for(register int j = 1; j <= m; j++){
		for(register int i = j; i <= m; i++){
			if(!e[i][j]) continue;
			if(i != j) swap(e[i], e[j]), f *= -1; //行列式交换
			break; 
		}
		if(!e[j][j]) return 0;
		res = res * e[j][j] % mod;
		int tem = power(e[j][j], mod - 2);
		for(register int k = j; k <= m; k++) e[j][k] = e[j][k] * tem % mod;
		for(register int i = j + 1; i <= m; i++)
			for(register int k = j, t = e[i][j]; k <= m; k++)
				e[i][k] = ((e[i][k] - t * e[j][k] % mod) % mod + mod) % mod;
	}
	return (res * f + mod) % mod;
}
signed main()
{
	initial();
	T = read();
	while(T--){
		n = read(), m = read();
		for(register int i = 1; i <= m; i++) x[i] = read(), y[i] = read();
		for(register int i = 1; i <= m; i++)
			for(register int j = 1; j <= m; j++) e[i][j] = (x[i] <= y[j]) ? C(y[j] - x[i] + n - 1, n - 1) : 0;
		printf("%dn", det());
	}
	return 0;
}

(LuoGu P7736) ([NOI2021]) 路径交点

(T) 组数据,每组给出 (k) 层点,第 (i) 层点有 (n_i) 个,其中 (n_1=n_k,n_1leq n_ileq 2n_1)。第 (i(1leq i<k)) 层的点仅会向第 (i + 1) 层的点连 (m_i) 条有向边,第 (k) 层点不向任何点连边。对于两条路径 (P,Q),设它们在第 (j) 层的连边为 ((P_j,P_{j+1}),(Q_j,Q_{j+1})),则称这两个路径在第 (j) 层有交点,当且仅当:

[(P_j - Q_j)(P_{j+1}-Q_{j+1})<0 ]

定义一个路径的总相交次数为所有边两两的相交次数之和。求在选出 (n_1) 条互不相交的路径,满足均以第一层点为起点,第 (k) 层点为终点的所有方案中,总相交次数为偶数的方案减去总相交次数为奇数的方案是多少,答案对 (998244353) 取模。

(2leq k,n_1leq 100,1leq Tleq 5)

(Sol)

偶数减去奇数,暗示行列式,再考虑相交次数,对于 (k=2) 的情况,两个路径相交,如果顺次匹配的话,当且仅当其对应的 (r) 中产生了一个逆序对。所以对于 (k=2),我们可以直接把原图的邻接矩阵当做 (M) 矩阵做 (LGV) 引理,这样得到的就是相交偶数次减去相交奇数次。

原因比较显然,考虑行列式的式子:

[det(M) = sum_{r} (-1)^{tau (r)}prod _{i =1}^n e(a_i,b_{r_i}) ]

等于是 (tau(r)) 偶数的时候是正,否则是负数,和原问比较完美的契合。

对于 (k > 2) 的情况,一个显然的想法是扩展上面的思路,(LGV) 引理要求的是路径条数,那我们就把每一层对应的邻接矩阵乘起来,就能得到方案了,记这个新矩阵为 (M)(LGV) 引理。

时间复杂度 (O(Tn^3k))

(code)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e2 + 10, mod = 998244353;
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
struct Matrix{
	int n, m, a[N][N];
	Matrix operator * (const Matrix &x){
		Matrix res; res.n = n; res.m = x.m;
		for(register int i = 1; i <= n; i++){
			for(register int j = 1; j <= x.m; j++){
				int add = 0;
				for(register int k = 1; k <= m; k++) add = (add + a[i][k] * x.a[k][j] % mod) % mod;
				res.a[i][j] = add;
			}
		}
		return res;
	}
	inline void clear(int x, int y){
		n = x, m = y;
		for(register int i = 1; i <= n; i++)
			for(register int j = 1; j <= m; j++) a[i][j] = 0;
	}
}A, B;
inline int power(int x, int k)
{
	int res = 1;
	while(k){
		if(k & 1) res = res * x % mod;
		x = x * x % mod, k >>= 1;
	}
	return res;
}
int T, n[N], m[N], e[N][N];
inline int det(int m)
{
	int res = 1, f = 1;
	for(register int i = 1; i <= m; i++)
		for(register int j = 1; j <= m; j++) e[i][j] = A.a[i][j];
	for(register int j = 1; j <= m; j++){
		for(register int i = j; i <= m; i++){
			if(!e[i][j]) continue;
			if(i != j) swap(e[i], e[j]), f *= -1; //行列式交换
			break; 
		}
		if(!e[j][j]) return 0;
		res = res * e[j][j] % mod;
		int tem = power(e[j][j], mod - 2);
		for(register int k = j; k <= m; k++) e[j][k] = e[j][k] * tem % mod;
		for(register int i = j + 1; i <= m; i++)
			for(register int k = j, t = e[i][j]; k <= m; k++)
				e[i][k] = ((e[i][k] - t * e[j][k] % mod) % mod + mod) % mod;
	}
	return (res * f + mod) % mod;
}
signed main()
{
	T = read();
	while(T--){
		int k = read();
		for(register int i = 1; i <= k; i++) n[i] = read();
		for(register int i = 1; i < k; i++) m[i] = read();
		A.clear(n[1], n[2]);
		for(register int i = 1, x, y; i <= m[1]; i++)
			x = read(), y = read(), A.a[x][y] = 1;
		for(register int i = 2; i < k; i++){
			B.clear(n[i], n[i + 1]);
			for(register int j = 1, x, y; j <= m[i]; j++)
				x = read(), y = read(), B.a[x][y] = 1;
			A = A * B;
		}
		printf("%dn", det(n[1]));
	}
	return 0;
}

完。

程序员灯塔
转载请注明原文链接:LGV 引理
喜欢 (0)